Leetcode一百题——翻转二叉树

给你一棵二叉树的根节点 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. 代码逻辑解析

代码主要分为两个部分：主控函数 invertTree 和负责具体执行的递归辅助函数 func。

• 主函数 invertTree： 首先进行边界条件的安全拦截。如果传入的根节点 root 为空，说明这是一棵空树，直接返回 NULL 即可。如果非空，则将其传入 func 函数开始递归处理。处理完成后，返回原先的根节点。

• 递归辅助函数 func： 这是实现翻转的核心部分。对于当前传入的 node，操作分为两步：

  1. 执行交换：声明一个 TreeNode* temp 作为临时变量，将 node->left 和 node->right 的指针指向互换。此时，当前节点本身的翻转已经完成。
  2. 向下递归：检查交换后的 node->left 和 node->right。如果它们不为空，则分别递归调用 func，让下一层的节点继续执行上述的交换过程。

‍

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) {
            return NULL;
        }
        
        func(root);
        return root;

    }
    void func (TreeNode* node) {
        TreeNode* temp;

        temp = node->left;
        node->left = node->right;
        node->right = temp;

        if (node->left != NULL) {
            func(node->left);
        }
        if (node->right != NULL) {
            func(node->right);
        }
    }
};

‍

3. 复杂度分析

• 时间复杂度：O(N)。其中 N 为二叉树的节点总数。在递归过程中，树上的每一个节点都会被精确地访问一次，并执行一次常数时间 O(1) 的指针交换操作，因此整体时间开销与节点总数成正比。
• 空间复杂度：O(H)。其中 H 为二叉树的高度。算法没有使用额外的数据结构来存储节点，内存消耗主要来自于递归调用时系统分配的函数栈空间。在最坏情况下（树退化成一条单向链表），递归深度达到 N，空间复杂度为 O(N)；在最好情况下（树完全平衡），递归深度为 logN，空间复杂度为 O(logN)。

‍