limanting 的个人博客

题目

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

我的答案

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
    if (!preorder.length || !inorder.length) {
        return null;
    }
    const root = new TreeNode(preorder[0]);
    const indexOfRoot = inorder.indexOf(preorder[0]);
    const leftInorder = inorder.slice(0, indexOfRoot);
    const rightInorder = inorder.slice(indexOfRoot + 1);
    const leftPreOrder = preorder.filter((item) => leftInorder.includes(item));
    const rightPreOrder = preorder.filter((item) => rightInorder.includes(item));
    root.left = buildTree(leftPreOrder, leftInorder);
    root.right = buildTree(rightPreOrder, rightInorder);
    return root;
};

这道题就是最基础二叉树还原。基本的概念就是，前序遍历的第一个值就是当前节点的值，然后这个值在中序遍历数组的的左边的子数组就是这个节点的左子树。

这道题利用的就是前序遍历和中序遍历的特质中确定的信息。

改进：

var buildTree = function (preorder, inorder) {
    if (!preorder.length || !inorder.length) {
        return null;
    }
    const root = new TreeNode(preorder[0]);
    const indexOfRoot = inorder.indexOf(preorder[0]);
    const leftInorder = inorder.slice(0, indexOfRoot);
    const rightInorder = inorder.slice(indexOfRoot + 1);
    const leftPreOrder = preorder.slice(1, leftInorder.length + 1);
    const rightPreOrder = preorder.slice(leftInorder.length + 1);
    root.left = buildTree(leftPreOrder, leftInorder);
    root.right = buildTree(rightPreOrder, rightInorder);
    return root;
};

因为前序遍历的左边一定在右边的前面，所以可以直接截断。