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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode105 从前序与中序遍历中构造二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含890字，纯文字阅读大概需要2分钟。

内容图文

根据一棵树的前序遍历与中序遍历构造二叉树。
思路：
1.根据前序数组，找到根节点
2.根据中序数组中的根节点，找到左子树的长度
3.根据左子树的长度，找到左右子树的前序数组和中序数组
4.递归调用，直到前序数组为null

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}
var buildTree = function(preorder, inorder) {

    //建立一个哈希表，从中查找数组下标
    let map = new Map();
    for (let i = 0; i < inorder.length; i++) {
       map.set(inorder[i],i)
    }
    const helper=(p_start,p_end,i_start,i_end)=>{
        if(p_start>p_end)  return null
        let root=preorder[p_start]
        let node = new TreeNode(root)
        let mid=map.get(root)
        let leftNum=mid-i_start
        node.left=helper(p_start+1,p_start+leftNum,i_start,mid-1)
        node.right=helper(p_start+leftNum+1,p_end,mid+1,i_end)
        return node
    }
    return helper(0,preorder.length-1,0,inorder.length-1)
};

内容总结

以上是互联网集市为您收集整理的leetcode105 从前序与中序遍历中构造二叉树全部内容，希望文章能够帮你解决leetcode105 从前序与中序遍历中构造二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---