leetcode|leetcode 105. 从前序与中序遍历序列构造二叉树 javascript
【leetcode|leetcode 105. 从前序与中序遍历序列构造二叉树 javascript】解题的关键在于要知道前序和中序的区别，
前序是根左右，中序是左根右
比如题目中给到的
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
可以知道根节点是3，然后可以从中序数组中得出左子树和右子树，分别是[9] 和 [15,20,7]
同样，知道左右子树之后，根据其数组长度，可以在前序数组中定位前序的左右子树，分别是[9] 和 [20,15,7]，这时候就要用到递归了，直到得到结果
递归的终止条件是，序列为空，返回null
序列只有一个元素(也就是叶子节点)，创造新的node，并直接返回，详见代码
/**
* 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 || preorder.length < 1){
return null;
}
let root = preorder[0];
let treeNode = new TreeNode(root);
if(preorder.length === 1) {
return treeNode;
}let rootIndex = inorder.indexOf(root);
let inLeftTree = inorder.slice(0, rootIndex);
let preLeftTree= preorder.slice(1, inLeftTree.length + 1);
let inRightTree = inorder.slice(rootIndex + 1, inorder.length);
let preRightTree = preorder.slice(preLeftTree.length + 1, preorder.length);
treeNode.left = buildTree(preLeftTree, inLeftTree);
treeNode.right = buildTree(preRightTree, inRightTree);
return treeNode;
};
推荐阅读
- leetcode 128. Longest Consecutive Sequence 最长连续序列(中等)
- 一笔写从前（二十二）
- 不见
- 猫国传(一)
- 算法面试冲刺|Leetcode 算法面试冲刺 热题 HOT 100 刷题（337 338 347 394 399）（六十八）
- Leetcode刷题复习|Leetcode 刷题必须Review 十七 Lintcode（423 492 541 421 575）
- leetcode|leetcode 739. Daily Temperatures 每日温度(中等)
- Redis 5.0 部分源码剖析
- Beautiful|Beautiful lies
- leetcode|leetcode 232. Implement Queue using Stacks 用栈实现队列(简单)