学习记录：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; // 如果树为空，直接返回 null

    const 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，即翻转后的树的根节点。

总结

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

原文地址：https://blog.csdn.net/weixin_48677331/article/details/142470156

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！