给定二叉树的含中序的任意两个遍历序列还原二叉树

思路：该二叉树能够还原的充分条件是这两个序列必含有一个中序遍历序列。因为通过中序遍历序列以及之外的任意一个序列能够退出左右子树的规模，然后递归地构建父亲节点。

Code:

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {        
        return dfs(pre, vin, 0, 0, pre.size());
    }
    
    /** * 中序遍历序***定子树的大小 * 先序遍历序***定子树的根 */
    
    TreeNode* dfs(vector<int> &pre,vector<int> &vin, int root, int start, int end) {
        if (start == end) return NULL;
        TreeNode* father = new TreeNode(pre[root]);
        for (register int i = start; i < end; i++) {
            if (pre[root] == vin[i]) {
                father->left = dfs(pre, vin, root+1, start, i);
                father->right = dfs(pre, vin, root+i-start+1, i+1, end);
                break;
            }
        }
        return father;
    }
};