0226. Invert Binary Tree ======================== 题目信息 -------- :题号: 0226 :难度: Easy :主题: 二叉树、深度优先搜索、广度优先搜索 :原题: `LeetCode 0226 `_ :重点: 每个节点交换左右子树、返回根节点、空树、结构变化 题目重述 -------- 给定二叉树根节点 ``root``,把树中每个节点的左子树和右子树互换,返回反转后的根节点。反转作用于整棵树,而不是只交换根节点的两个直接孩子。 树中节点数位于 ``[0, 100]``,节点值位于 ``[-100, 100]``。空树反转后仍返回空引用。题目返回的是完成结构交换后的树,节点值本身保持不变。 自建示例 -------- 多层子树同时交换: .. code-block:: text 输入:root = [5, 3, 8, 1, 4, 7, null] 输出:[5, 8, 3, null, 7, 4, 1] 解释:根节点的左右子树互换;原节点 3 的孩子 1 和 4、原节点 8 的孩子 7 和空位置也分别互换。 空树: .. code-block:: text 输入:root = [] 输出:[] 解释:没有节点需要交换,结果仍为空树。 递归交换子树 ------------ 反转一棵树的根节点时,先交换它的左右孩子,再对交换后的两个子树递归处理。递归函数返回的仍是原节点, 只是该节点以下的每条左右方向都被反转;空指针是递归基例。 不要只交换根节点:根下的每个节点也必须交换自己的两个子树。交换后再递归是安全的, 因为两个新孩子正是原来的两个互不相交子树,分别继续反转即可。 正确性说明 ---------- 对树高归纳。空树不需要变化;假设左右子树分别能被递归正确反转。当前节点交换左右指针后, 原左子树成为右子树、原右子树成为左子树,再由归纳假设完成各自内部反转,因此当前节点及其整棵子树符合镜像结构。 节点值从未改动,返回原根节点即可。 C++ 实现 -------- .. code-block:: cpp class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return nullptr; std::swap(root->left, root->right); invertTree(root->left); invertTree(root->right); return root; } }; 代码分析 -------- 每个节点恰好访问一次,时间复杂度为 ``O(n)``;递归栈深度等于树高,额外空间为 ``O(h)``, 最坏退化树时为 ``O(n)``。算法只重接已有指针,不创建或删除节点,也不依赖节点值的大小关系。