资讯详情

题目

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

代码

方法一：递归

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]
) -> Optional[TreeNode]:
if not root:
return
cur=self.invertTree(root.left)
root.left=self.invertTree(root.right)
root.right=cur
return root

方法二：栈迭代

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]
) -> Optional[TreeNode]:
if not root:
return
stack=[root]
while stack:
node=stack.pop(
)
if node:
stack.append(node.left)
stack.append(node.right)
node.left,node.right=node.right,node.left
return root

方法三：队迭代

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]
) -> Optional[TreeNode]:
if not root:
return
queue=deque([root]
)
while queue:
for _
in range(len(queue)):
node=queue.popleft(
)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
node.left,node.right=node.right,node.left
return root

这道题的方法和求二叉树的深度方法一致