leetcode——从先序遍历与中序遍历序列构造二叉树

2021年9月19日 6点热度 0条评论 来源: 发量惊人

题目
根据一棵树的前序遍历与中序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:

二叉树深度遍历

  • 先序遍历:DLR
  • 中序遍历:LDR
  • 后序遍历:LRD

根据中序和先序遍历序列重构二叉树

  • 由先序遍历特点可知,先序遍历第一个数据为根节点数据,则该二叉树的根节点值为preorder[0]=3
  • 由中序遍历特点可知,根节点左边为左子树中序遍历结果,即[9]。根节点右边为右子树中序遍历结果,及[15,20,7]
  • 根据左/右子树中序遍历的结果和preorder可知左/右子树先序遍历的结果
  • 递归左/右子树直到先序遍历结果的数组长度为1

代码实现

/** * 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) { 
    
    var result = null

    if(preorder.length > 1){ 
        //根节点的值
        var root = preorder.shift()
        //根节点在中序遍历数组中的索引
        var rootIndex = inorder.indexOf(root)

        //左子树的中序遍历结果
        var inLeft = inorder.slice(0,rootIndex)
        //右子树中序遍历结果
        var inRight = inorder.slice(rootIndex+1)

        //左子树先序遍历的结果
        var preLeft = preorder.slice(0,rootIndex)
        var preRight = preorder.slice(rootIndex)

        result = { 
            val: root,
            left: buildTree(preLeft,inLeft),
            right: buildTree(preRight,inRight)
        } 
    }else if(preorder.length == 1){ 
        result = { 
            val: preorder[0],
            left: null,
            right: null
        }
    }
    return result
};
    原文作者:发量惊人
    原文地址: https://blog.csdn.net/weixin_42937036/article/details/106293076
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。