题解 | #重建二叉树#

 * 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) {
        int n=pre.size();
        int m=vin.size();
        if(!n||!m)
            return NULL;
        TreeNode* root=new TreeNode(pre[0]);
        TreeNode* cur=root;
        stack<TreeNode*>s;
        for(int i=1,j=0;i<n;i++){
            if(cur->val!=vin[j]){
                cur->left=new TreeNode(pre[i]);
                s.push(cur);
                cur=cur->left;
            }
            else {
                j++;
                while(!s.empty()&&s.top()->val==vin[j]){
                    cur=s.top();
                    s.pop();
                    ++j;
                }
                cur->right=new TreeNode(pre[i]);
                cur=cur->right;
            }
        }
        return root;
    }
};