本文共 1648 字，大约阅读时间需要 5 分钟。
反转二叉树
你是否遇到过在白板上无法用手比划出二叉树反转的难题？这则来自Google的趣味故事似乎印证了这件事。那么，如何在代码中实现二叉树的反转呢？我们一起来探讨一下这个问题。
给定以下二叉树结构：
4/
2 7/ \ / 1 3 6 9目标是将其反转为：
4/
7 2/ \ / 9 6 3 1这个问题看起来像是一种二叉树的镜像反转，但实际上涉及到交换子节点的位置。我们可以通过使用栈来实现这一点，因为栈非常适合处理后序遍历。
算法思路：
这种方法通过不断交换左右子节点的位置，最终实现了二叉树的反转。
代码实现：
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)。
转载地址：http://ejgfk.baihongyu.com/