本文共 1765 字,大约阅读时间需要 5 分钟。
function TreeNode(val){ this.val = val; this.left = null; this.right = null;}function createTreeByLevelOrder(levelOrder){ let queue = [] // queue 里面存储的是新建的树的层序遍历的节点关系 // queue中是两层节点之间的父子关系 if(levelOrder[0]){ let node = levelOrder.shift() var root = new TreeNode(node) queue.push(root) while(queue.length && levelOrder.length){ // 只有在levelOrder的元素不为null的时候,才会新建节点,然后向queue中push,所以用queue.length作为循环判断 // 使用levelOrder.length来判断是否有剩余节点,不管最后一个节点之后是否填充null,都可以;如果最后节点之后没有填充null的话,防止死循环 let par = queue.shift() let pleft = levelOrder.shift() if(pleft !== null){ par.left = new TreeNode(pleft) queue.push(par.left) } let pright = levelOrder.shift() if(pright !== null){ par.right = new TreeNode(pright) queue.push(par.right) } } } return root}
// definition for a binary tree node function TreeNode(val){ this.val = val; this.left = null; this.right = null;}let preOrderArr=['a','b','d','#','f','#','#','#','c','#','e','#','#']function createTreeByPre(arr){ let root = null if(arr[0]){ let nodeVal = arr.shift() if(nodeVal !== '#'){ root = new TreeNode(nodeVal) root.left = createTreeByPre(arr) root.right = createTreeByPre(arr) } } return root // 这里必须要return一个root,因为root是一直更新的。从栈中pop的最后一个root就是根节点。如果不return的话,最后一个root就是最后一个节点}let tree = createTreeByPre(preOrderArr)
var buildTree = function(preorder, inorder) { if(preorder.length === 0) return null const root = new TreeNode(preorder[0]) const mid = inorder.indexOf(preorder[0]) root.left = buildTree(preorder.slice(1, mid+1), inorder.slice(0, mid)) root.right = buildTree(preorder.slice(mid+1), inorder.slice(mid+1)) return root};
转载地址:http://tzxzi.baihongyu.com/