力扣(leetcode) 226. 翻转二叉树 (递归法) (迭代法) 图解过程--一看就懂_反转二叉树 将左边的二叉树反转成右边的二叉树 递归分析

题目在这:https://leetcode-cn.com/problems/invert-binary-tree/

法一:(递归法)

思路分析

看上面的图，这里只列举了三层的情况， 每一个节点都要交换他的左右子树。根节点也不例外。

使用容易理解的迭代法，交换左右子树，然后递归左子树，递归右子树。

这个方法大家一看就懂。

完整代码:

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None

        root.left, root.right = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root
1
2
3
4
5
6
7
8
9
10
11

法二:(迭代法)

思路分析

建立一个队列，也可以理解为列表。首先把根节点加进去，然后交换左右子树，然后看左右子树是否还有孩子，有的话也就加进去。理解类似于递归，

完整代码

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        queue = [root]
        while queue:
            cur_root = queue.pop()
            cur_root.left, cur_root.right = cur_root.right, cur_root.left
            if cur_root.left:
                queue.append(cur_root.left)
            if cur_root.right:
                queue.append(cur_root.right)

        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14