翻转二叉树 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

要点

对于根节点，它的左右儿子必须交换，即左儿子变成右儿子，右儿子变成左儿子。
对于根节点的左右子树，也需要翻转其内部节点。这是一个和原问题相似的子问题，看完视频后，你知道，这可以用递归解决。

算法

递归调用 invertTree(root.left)，获取到左子树翻转后的结果 left。
递归调用 invertTree(root.right)，获取到右子树翻转后的结果 right。
交换左右儿子，即更新 root.left 为 right，更新 root.right 为 left。
返回 root。
递归边界：如果 root 是空节点，返回空。

晕递归的同学，请看视频：深入理解递归【基础算法精讲 09】

写法一

Python 解法1C++ 解法1

python

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        left = self.invertTree(root.left)  # 翻转左子树
        right = self.invertTree(root.right)  # 翻转右子树
        root.left = right  # 交换左右儿子
        root.right = left
        return root

cpp

// C++ 版待补充

Python 解法2C++ 解法2

python

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        root.right, root.left = self.invertTree(root.left), self.invertTree(root.right)
        return root

cpp

// C++ 版待补充

C++ 解法3

cpp

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        auto left = invertTree(root->left); // 翻转左子树
        auto right = invertTree(root->right); // 翻转右子树
        root->left = right; // 交换左右儿子
        root->right = left;
        return root;
    }
};

写法二

也可以先交换左右儿子，然后递归处理左右子树。

Python 解法4C++ 解法4

python

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        root.left, root.right = root.right, root.left  # 交换左右儿子
        self.invertTree(root.left)  # 翻转左子树
        self.invertTree(root.right)  # 翻转右子树
        return root

cpp

// C++ 版待补充

C++ 解法5

cpp

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        swap(root->left, root->right); // 交换左右儿子
        invertTree(root->left); // 翻转左子树
        invertTree(root->right); // 翻转右子树
        return root;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是二叉树的节点个数。
空间复杂度： $O (n)$ 。最坏情况下，二叉树退化成一条链，递归需要 $O (n)$ 的栈空间。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

要点 ​

算法 ​

写法一 ​

写法二 ​

复杂度分析 ​

分类题单 ​

要点

算法

写法一

写法二

复杂度分析

分类题单