vvrf / DSA.log

问题拆解

翻转的效果是让整棵树沿中轴左右镜像。乍看要动到每一层的每个节点，似乎很繁琐，但只要盯住根节点就会发现：翻转整棵树，无非是把根的左右孩子交换，然后让换过去的两棵子树各自也完成翻转。

这是一个可以原地递归下去的操作——每一层都只做“交换 + 下探”这一件事。

一个看似要动全局的变换，往往能拆成“当前层做一步，剩下的交给子问题”。

交换后递归

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

def invertTree(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    if let Some(node) = &root {
        let mut n = node.borrow_mut();
        let left = n.left.take();
        n.left = n.right.take();
        n.right = left;
        Self::invert_tree(n.left.clone());
        Self::invert_tree(n.right.clone());
    }
    root
}

Python 的元组赋值让交换一行搞定，不需要临时变量。先交换还是先递归其实都行：因为交换只影响当前节点的两个指针，不改变子树内部结构，两种顺序得到的结果一致。空树直接返回，是递归自然收口的地方。

如果不想用递归栈，也可以借助一个队列做层序遍历，对每个出队的节点交换其左右孩子，再把孩子入队，效果完全相同。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个节点被交换一次
空间	`O(h)`	递归栈深度等于树高

可以迁移的模式

“对整棵结构做某种变换”常能归约成“对根做一步局部操作 + 对子结构递归同样的操作”；
交换两个引用用元组赋值最干净，省掉临时变量；
判断递归顺序是否要紧，只需看这一步会不会破坏后续递归依赖的结构。

能就地改结构的树问题，通常比“重建一棵新树”写得更短。