Leetcode 226. 翻转二叉树

 

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

tips：这道题很简单，可以用 递归 和 非递归 两种方法来解。

先来看递归的方法，写法非常简洁，只需要三行代码搞定：交换当前左右节点，然后直接调用递归即可 。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# 递归
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return 
        root.left,root.right=root.right,root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

非递归的解法跟二叉树的层序遍历一样，需要用 queue 来辅助。

首先把根节点排入队列中，然后从队中取出来，交换其左右节点，如果存在则分别将左右节点在排入队列中，以此类推直到队列中没有节点了再停止循环，最后返回 root 即可。

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