LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

思路

title真是长..给前序遍历和中序遍历，构造二叉树。
前序遍历就是Node, Left, Right，而中序遍历是Left, Node, Right，因此给一个前序遍历的序列，他的第一个节点肯定就是那个Node，然后在中序序列里找，就能把序列分成左中右三部分。
自然地就要用递归啦~

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTreeSub(const vector<int>& preorder, int p_start, int p_end,
                            const vector<int>& inorder, int i_start, int i_end){
        int pivot = preorder[p_start];
        TreeNode* root = new TreeNode(pivot);
        int indexPivotInorder = -1;
        for(indexPivotInorder=i_start; indexPivotInorder<=i_end; indexPivotInorder++){
            if(inorder[indexPivotInorder] == pivot)
                break;
        }
        int len_left = indexPivotInorder-i_start;
        if(indexPivotInorder > i_start){
            //if we still have left part
            root->left = buildTreeSub(preorder, p_start+1, p_start+len_left, inorder, i_start, indexPivotInorder-1);
        }
        if(indexPivotInorder < i_end){
            //if we still have right part
            root->right = buildTreeSub(preorder, p_start+len_left+1, p_end, inorder, indexPivotInorder+1, i_end);
        }
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty() || inorder.empty())
            return NULL;
        return buildTreeSub(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};