Leetcode刷题(第105题)——从前序与中序遍历序列构造二叉树

x33g5p2x  于2022-03-10 转载在 其他  
字(1.2k)|赞(0)|评价(0)|浏览(272)

一、题目

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

二、示例

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

三、解题思路
本题给我们前序遍历和中序遍历,这样我们就可以确定一个树。本题中我们使用的是递归算法。本题以preorder = [3,9,20,15,7]inorder = [9,3,15,20,7]为例。从先序遍历中我们可以知道根节点是3,然后我们在进行查找在中序遍历中3的左边为根节点的左子树的中序遍历,3的右边为根节点的右子树的中序遍历,然后再从preorder中查找左子树的先序遍历和右子树的先序遍历。最终再次使用递归算法即可。
四、代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    let firstOne = preorder[0]
    let node = new TreeNode(firstOne)
    let index = inorder.findIndex(value => value === firstOne)
    let leftPreOrder = preorder.slice(1, index + 1)
    let rightPreOrder = preorder.slice(index + 1)
    let leftInOrder = inorder.slice(0, index)
    let rightInOrder = inorder.slice(index + 1)
    if(leftInOrder.length && leftPreOrder) {
        node.left = buildTree(leftPreOrder, leftInOrder)
    } 
    if(rightInOrder.length && rightPreOrder.length) {
        node.right = buildTree(rightPreOrder, rightInOrder)
    }
    return node
};

五、总结

相关文章