Invert Binary Tree

226. 翻转二叉树

分析

递归结束条件
- 如果当前节点 root 为 nullptr，直接返回 nullptr，表示已到达叶子节点的空子树
交换左右子树
- 使用 std::swap 交换当前节点的左子树和右子树
递归处理子树
- 对交换后的左子树调用 invertTree
- 对交换后的右子树调用 invertTree
返回结果
- 当所有节点都完成翻转后，返回根节点 root

时间复杂度

每个节点被访问一次，执行左右子树的交换操作，因此时间复杂度为 O(n)，其中 n 是节点总数

空间复杂度

递归调用的栈深度取决于树的高度。在最坏情况下（单链表形式的树），空间复杂度为 O(n)；在最优情况下（完全平衡二叉树），空间复杂度为 O(logn)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


// DFS
class Solution {
public:
    TreeNode* invertTree(TreeNode* root)
    {
        if (!root)
            return nullptr;  // 若节点为空，直接返回
        std::swap(root->left, root->right);  // 交换左右子树
        invertTree(root->left);  // 递归处理左子树
        invertTree(root->right);  // 递归处理右子树
        return root;  // 返回翻转后的树根节点
    }
};

// BFS
class Solution {
public:
    TreeNode* invertTree(TreeNode* root)
    {
        if (!root) return nullptr;

        std::queue<TreeNode*> q;
        q.push(root);  // 将根节点入队

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            // 交换左右子树
            std::swap(node->left, node->right);

            // 将子节点入队
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }

        return root;
    }
};