当前位置：首页 > article >正文

学习记录：js算法（五十六）：从前序与中序遍历序列构造二叉树

article 2024/10/7 20:33:25

文章目录

- 从前序与中序遍历序列构造二叉树
- - 我的思路
  - 网上思路
- 总结

从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]

我的思路
递归
网上思路
栈

我的思路

var buildTree = function (preorder, inorder) {
    const build = (preStart, inStart, inEnd) => {
        if (inStart > inEnd) return null; // 终止条件：没有节点要构建了

        // 先序遍历中的第一个节点就是当前子树的根节点
        const rootVal = preorder[preStart];
        const root = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置，以此划分左右子树
        const index = inorder.indexOf(rootVal, inStart, inEnd + 1);

        // 递归构建左子树和右子树
        root.left = build(preStart + 1, inStart, index - 1);
        root.right = build(preStart + index - inStart + 1, index + 1, inEnd);

        return root;
    };

    return build(0, 0, inorder.length - 1);
}

讲解

先序遍历：先序遍历的顺序是根节点 -> 左子树 -> 右子树。这意味着先序遍历的第一个元素总是树的根节点。
中序遍历：中序遍历的顺序是左子树 -> 根节点 -> 右子树。通过中序遍历，可以明确知道根节点在哪些元素的左侧，哪些元素的右侧，从而区分左右子树。
递归构建：知道了根节点，就可以在中序遍历中找到根节点的位置，这个位置将中序序列分成两部分，左边是左子树的中序遍历，右边是右子树的中序遍历。同时，根据先序遍历中根节点之后的元素个数，可以确定左右子树的先序遍历范围。然后递归地在左右子树的先序和中序序列中构建子树。

网上思路

var buildTree = function (preorder, inorder) {
    if (preorder.length === 0 || inorder.length === 0) {
        return null;
    }

    const root = new TreeNode(preorder[0]);
    const stack = [root];
    let inorderIndex = 0;

    for (let i = 1; i < preorder.length; i++) {
        const node = new TreeNode(preorder[i]);

        // 将栈顶元素与当前节点进行连接
        let topNode = stack[stack.length - 1];

        // 如果栈顶元素的值与中序遍历的当前值相同，则说明当前节点是栈顶元素的右子节点
        if (topNode.val === inorder[inorderIndex]) {
            while (stack.length > 0 && stack[stack.length - 1].val === inorder[inorderIndex]) {
                topNode = stack.pop();
                inorderIndex++;
            }
            topNode.right = node; // 连接到右子节点
        } else {
            topNode.left = node; // 连接到左子节点
        }

        // 将当前节点入栈
        stack.push(node);
    }

    return root;
}

讲解

首先检查 preorder 和 inorder 数组是否为空。
创建根节点并将其入栈。
遍历 preorder 数组，从第二个元素开始。
对于每个新节点，检查栈顶元素是否与当前 inorder 中的值相同：
如果相同，则弹出栈顶元素，并继续检查，直到栈顶元素与 inorder 中的值不同。
如果不同，则将新节点作为栈顶元素的左子节点。
最后，将新节点入栈。