Leetcode-Day11

Posted on   |   In

从零开始Leetcode – Day 11

Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
今天把 preorder, inorder, postorder. traversal 就是MLR, LMR, LRM. 递归思想， 每次看成一个3个节点的树。

http://blog.csdn.net/linhuanmars/article/details/24389549
明天早上在把它完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    
    if(!preorder || !inorder){
        return null;
    }
    var map = [];
    for(var i = 0; i < inorder.length; i++){
        map.push(inorder[i]);
    }
    return helper(preorder, 0,preorder.length -1, inorder, 0 , inorder.length -1, map);
    
    function helper(preorder, preL, preR, inorder, inL, inR, map){
        if(preL > preR || inL > inR){
            return null;
        }
        var root = new TreeNode(preorder[preL]);
        var index = map.indexOf(root.val);
        root.left = helper(preorder, preL +1, index-inL +preL, inorder, inL, index-1, map);
        root.right = helper(preorder, preL + index + inL +1, preR, inorder, index+1, inR ,map);
        return root;
    }
};