学习记录：js算法（四十三）：翻转二叉树

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

图一：

图二：

示例 1：（如图一）
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]示例 2：（如图二）
输入：root = [2,1,3]
输出：[2,3,1]示例 3：
输入：root = []
输出：[]

我的思路
循环
网上思路
递归、栈

我的思路

var invertTree = function (root) {if (!root) return null;const queue = [root];while (queue.length > 0) {const current = queue.shift();[current.left, current.right] = [current.right, current.left];if (current.left) queue.push(current.left);if (current.right) queue.push(current.right);}return root;
};

讲解

1. 首先检查根节点是否为空，如果为空，直接返回 null。
2. 使用一个数组 nodes 来存储待处理的节点，初始化时将根节点放入数组。
3. 使用 for 循环遍历数组中的节点：
   • 取出当前节点 current。
   • 交换当前节点的左右子树。
   • 如果当前节点的左子节点不为空，将其加入数组；如果右子节点不为空，也加入数组。
4. 当所有节点处理完毕后，返回翻转后的根节点。

网上思路

递归

var invertTree = function (root) {if (!root) return null; // 如果树为空，直接返回 null// 递归翻转左右子树const left = invertTree(root.left);const right = invertTree(root.right);// 交换左右子树root.left = right;root.right = left;return root; // 返回翻转后的根节点
}

讲解

1. 基线条件：首先检查当前节点 root 是否为空。如果是，直接返回 null。
2. 递归调用：
   • 使用 invertTree(root.left) 递归翻转左子树，并将结果存储在 left 变量中。
   • 使用 invertTree(root.right) 递归翻转右子树，并将结果存储在 right 变量中。
3. 交换左右子树：将当前节点的左子树设置为 right，右子树设置为 left。
4. 返回根节点：返回当前节点 root，以便在更高层的递归中继续处理。

栈

var invertTree = function (root) {if (!root) return null; // 如果树为空，直接返回 nullconst stack = [root]; // 使用栈来存储节点while (stack.length > 0) {const current = stack.pop(); // 取出栈顶的节点// 交换当前节点的左右子树[current.left, current.right] = [current.right, current.left];// 将非空的左右子节点加入栈if (current.left) stack.push(current.left);if (current.right) stack.push(current.right);}return root; // 返回翻转后的根节点
}

详解

1. 基线条件：首先检查根节点 root 是否为空。如果是，直接返回 null。
2. 栈初始化：使用一个数组 stack 来模拟栈，初始化时将根节点放入栈。
3. 循环处理：
   • 当栈不为空时，弹出栈顶节点 current。
   • 交换当前节点的左右子树。
   • 如果当前节点的左子节点不为空，将其压入栈；如果右子节点不为空，也压入栈。
4. 返回根节点：返回当前节点 root，即翻转后的树的根节点。

总结

解法挺多的，但是核心是一样的