本文共 1648 字，大约阅读时间需要 5 分钟。

反转二叉树

你是否遇到过在白板上无法用手比划出二叉树反转的难题？这则来自Google的趣味故事似乎印证了这件事。那么，如何在代码中实现二叉树的反转呢？我们一起来探讨一下这个问题。

给定以下二叉树结构：

4/

目标是将其反转为：

4/

这个问题看起来像是一种二叉树的镜像反转，但实际上涉及到交换子节点的位置。我们可以通过使用栈来实现这一点，因为栈非常适合处理后序遍历。

算法思路：

这种方法通过不断交换左右子节点的位置，最终实现了二叉树的反转。

代码实现：

public class Solution {    public TreeNode invertTree(TreeNode root) {        if (root == null) {            return null;        }        Stack stack = new Stack();        stack.push(root);        TreeNode tmp, left;        while (!stack.empty()) {            tmp = stack.pop();            if (tmp.left == null && tmp.right == null) {                continue;            }            if (tmp.left == null) {                tmp.left = tmp.right;                tmp.right = null;                stack.push(tmp.left);                continue;            }            if (tmp.right == null) {                tmp.right = tmp.left;                tmp.left = null;                stack.push(tmp.right);                continue;            }            left = tmp.left;            tmp.left = tmp.right;            tmp.right = left;            stack.push(tmp.left);            stack.push(tmp.right);        }        return root;    }}

代码解释：

通过这种方法，我们可以轻松地实现二叉树的反转。这个算法的时间复杂度为O(h)，其中h是树的高度，空间复杂度为O(h)。