[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;
}