0226. Invert Binary Tree¶
题目信息¶
- 题号:
0226
- 难度:
Easy
- 主题:
二叉树、深度优先搜索、广度优先搜索
- 原题:
- 重点:
每个节点交换左右子树、返回根节点、空树、结构变化
题目重述¶
给定二叉树根节点 root,把树中每个节点的左子树和右子树互换,返回反转后的根节点。反转作用于整棵树,而不是只交换根节点的两个直接孩子。
树中节点数位于 [0, 100],节点值位于 [-100, 100]。空树反转后仍返回空引用。题目返回的是完成结构交换后的树,节点值本身保持不变。
自建示例¶
多层子树同时交换:
输入:root = [5, 3, 8, 1, 4, 7, null]
输出:[5, 8, 3, null, 7, 4, 1]
解释:根节点的左右子树互换;原节点 3 的孩子 1 和 4、原节点 8 的孩子 7 和空位置也分别互换。
空树:
输入:root = []
输出:[]
解释:没有节点需要交换,结果仍为空树。
递归交换子树¶
反转一棵树的根节点时,先交换它的左右孩子,再对交换后的两个子树递归处理。递归函数返回的仍是原节点, 只是该节点以下的每条左右方向都被反转;空指针是递归基例。
不要只交换根节点:根下的每个节点也必须交换自己的两个子树。交换后再递归是安全的, 因为两个新孩子正是原来的两个互不相交子树,分别继续反转即可。
正确性说明¶
对树高归纳。空树不需要变化;假设左右子树分别能被递归正确反转。当前节点交换左右指针后, 原左子树成为右子树、原右子树成为左子树,再由归纳假设完成各自内部反转,因此当前节点及其整棵子树符合镜像结构。 节点值从未改动,返回原根节点即可。
C++ 实现¶
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)。算法只重接已有指针,不创建或删除节点,也不依赖节点值的大小关系。