题解 | #JZ7 重建二叉树#

//递归 ; 栈辅助遍历
/**
 * 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) {
        if (pre.empty() || vin.empty()) return nullptr;    //遍历为空则返回空
        
        TreeNode * head = new TreeNode(pre[0]);        //新建根节点
        
        auto vinIt = find(vin.begin(), vin.end(), pre[0]);    //在中序遍历中找到根节点
        int leftCnt = vinIt-vin.begin();        //根节点的左子树节点个数
        
        vector<int> leftVin(vin.begin(), vinIt);    //根节点左边为左子树
        vector<int> rightVin(vinIt+1, vin.end());    //根节点右边为右子树，跳过根节点
        vector<int> leftPre(pre.begin()+1, pre.begin()+1+leftCnt);    //跳过根节点，左子树拷贝
        vector<int> rightPre(pre.begin()+1+leftCnt, pre.end());    //跳过左子树，右子树拷贝
        
        head->left = reConstructBinaryTree(leftPre, leftVin);
        head->right = reConstructBinaryTree(rightPre, rightVin);
        
        return head;
    } */
    
    //栈辅助方法
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if (pre.empty()) return nullptr;
        stack<TreeNode*> nodeStack;
        //前序的第一个其实就是根节点， 中序：根左右 前序:左根右
        TreeNode *root = new TreeNode(pre[0]);
        TreeNode *cur = root;
        for (int i = 1, j = 0; i < pre.size(); i++) { 
			if (cur->val != vin[j]) { //查找左子树，找到左叶之前依次压入上层节点
				cur->left = new TreeNode(pre[i]); 
				nodeStack.push(cur); 
				cur = cur->left; 
			} else { //找到左叶，添加右子树，弹出并指向上层根节点
				j++; 
				//找到合适的cur，然后确定他的右节点
				while (!nodeStack.empty() && nodeStack.top()->val == vin[j]) { 
					cur = nodeStack.top(); 
                    nodeStack.pop();
					j++; 
				} 
				//给cur添加右节点 
				cur = cur->right = new TreeNode(pre[i]); 
			} 
		} 
		return root; 
    }
};