[Easy] 翻转二叉树 Invert a Binary Tree

2024年2月17日

💎 加入 E+ 成長計畫 如果你喜歡我們的內容,歡迎加入 E+,獲得更多深入的軟體前後端內容

翻转二叉树 Invert a binary tree 是程式面试中,很常会考的入门考题。在这个面试题中,我们要把下图左二叉树,翻转成下图右。

可以看到:

  • 4 节点底下的 2 与 7 位置对调
  • 2 节点底下的 1 与 3 位置对调
  • 7 节点底下的 6 与 9 位置对调
     4                 4
   /   \             /   \
  2     7           7     2
 / \   / \         / \   / \
1   3 6   9       9   6 3   1

如何翻转二叉树?

要怎么翻转一个二叉树呢?很简单,我们可以透过递回 recursion 的概念。递回就是把问题拆解成子问题,然后在函式中呼叫函式自己,来解决子问题。

以翻转二叉树来说,我们可以先翻转 4 底下的 7 与 2。

        4
       / \
      7   2
     / \ / \
    6  9 1  3
// 4 底下的 7 <-> 2 对调

接着利用递回的概念,往下走,翻转 7 底下的 6 与 9。

        4
       / \
      7   2
     / \ / \
    9  6 1  3
// 7 底下的 6 <-> 9 对调

同样地,翻转 2 底下的 1 与 3。

        4
       / \
      7   2
     / \ / \
    9  6 3  1
// 2 底下的 1 <-> 3 对调

一步步来看的话,会是这样。


 原始二叉树            步骤 2:            步骤 3:            步骤 4:
     4                 4                 4                 4
   /   \             /   \             /   \             /   \
  2     7           7     2           7     2           7     2
 / \   / \         / \   / \         / \   / \         / \   / \
1   3 6   9       6   9 1   3       9   6 1   3       9   6 3   1

翻转二叉树 JavaScript 代码

接着一起来看看代码吧!

// 定义 invertTree 函式,会接收根节点
function invertTree(root) {
  // 设定递回终止条件:如果没有节点就停止,返回 null
  if (root === null) return null;

  // 交换左右子节点,需要一个 temp 变数来暂存 root.left
  const temp = root.left;
  root.left = root.right;
  root.right = temp;

  // 递回呼叫 invertTree 自己,分别传入左右的子节点
  invertTree(root.left);
  invertTree(root.right);

  // 返回根节点
  return root;
}
🧵 如果你想收到最即時的內容更新,可以在 FacebookInstagram 上追蹤我們