二叉树反转操作示意图

AWS AI 直播！

binary tree你能把一个 a沿其纵轴倒置吗？这是一个著名的问题，因这条推文而广为人知：

Google：我们90%的工程师都在使用你写的软件（Homebrew），但你连在白板上反转二叉树都做不到，所以滚蛋吧。

— Max Howell (@mxcl) 2015年6月10日

假设有binary tree这样一个：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

进行倒置运算将导致：

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

树节点的定义如下：

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

本文最初发表于https://algodaily.com，我在该网站上维护一个技术面试课程，并为有抱负的开发者撰写思考性文章。

Homebrew这是作者Max Howell 在谷歌面试中答错的著名问题。希望这能避免你遭遇同样的厄运！

让我们来思考一下暴力破解——如果不使用任何巧妙的算法，我们该如何解决？我们可以从一个非常基本的输入开始，如下所示：

  1
 / \
2   3

所以，要垂直翻转，我们从第 0 行开始1，那里没有任何内容需要翻转或交换，它会保持原位。现在我们已经处理完了第一行。

接下来是第二个例子，我们遇到2和3，所以我们交换它们得到：

  1
 / \
3   2

有意思，这似乎完全颠倒了！当有多个节点时，是不是只要交换一下位置就行了？

但如果每层需要交换的节点超过两个呢？如果有多一层，情况可能如下所示：

      1
     / \
    3   2
   / \   \
  4   5   3

最后一行目前是有方向性的4 -> 5 -> 3，但我们希望结果是3 -> 5 -> 4正确反转的。

然而，我们可以通过两次单独的交换来实现这一点。请注意，以下是我们交换4和5得到5 -> 4，然后再5 -> 4与交换 的结果3。

      1
     / \
    2   3
   /   / \
  3   5   4

综上所述：我们可以执行按顺序遍历，并在每次迭代中进行交换。

读者指出，如果处理的是一棵非常大的二叉树，递归解决方案可能会因为调用栈的大小而导致问题。有两种方法可以解决这个问题：

1. 使用栈来模拟递归
2. 使用队列，以广度优先搜索的方式逐层访问，并交换左右节点来反转树。

最终代码如下所示：

function invertTree(head) {
  if (head) {
    var temp = head.left;
    head.left = head.right;
    head.right = temp;

    invertTree(head.left);
    invertTree(head.right);
  }

  return head;
}

请访问AlgoDaily.com查看更多技术难题的视觉教程，并订阅我们的每日编程问题简报！