Easy

题目描述

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

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100

解题思路

这是一道经典的二叉树递归题目，有多种解法：

1. 递归解法（推荐）：

  • 翻转二叉树的核心思想是交换每个节点的左右子树
  • 对于每个节点，先递归翻转其左右子树，然后交换左右子树的位置
  • 递归的终止条件是当前节点为空

2. 迭代解法（BFS）：

  • 使用队列进行层序遍历
  • 对每个访问到的节点，交换其左右子树
  • 将非空的左右子节点加入队列继续处理

3. 迭代解法（DFS）：

  • 使用栈进行深度优先遍历
  • 对每个访问到的节点，交换其左右子树

递归解法代码简洁、思路清晰，是最推荐的解法。时间复杂度为O(n)，其中n是树中节点的数量，因为需要访问每个节点一次。空间复杂度为O(h)，其中h是树的高度，主要是递归调用栈的开销。

代码实现

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

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

public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        // 递归翻转左右子树
        TreeNode left = InvertTree(root.left);
        TreeNode right = InvertTree(root.right);
        
        // 交换左右子树
        root.left = right;
        root.right = left;
        
        return root;
    }
}

var invertTree = function(root) {
    if (!root) return null;
    
    let temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型递归解法迭代解法
时间复杂度O(n)O(n)
空间复杂度O(h)O(w)

其中：

  • n 表示二叉树中节点的总数
  • h 表示二叉树的高度，最坏情况下为 O(n)
  • w 表示二叉树的最大宽度，最坏情况下为 O(n)

相关题目