题解 | #重建二叉树#

题目主要信息:

给定一个二叉树的前序遍历数组和中序遍历数组，要求还原该二叉树，并返回其头结点
二叉树中没有重复的结点值

具体思路:

首先我们分析一下两个遍历数组的特点：对于二叉树的前序遍历，我们知道序列的第一个元素必定是根结点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根结点将二叉树分成了左右子树两个部分，如下图所示（同一颜色即同一层级的根结点和其左右子树）： alt

二叉树遍历得到的题目给出的两个数组，要重建依然还得靠遍历。我们这里选择非递归前序遍历。

step 1：首先判断，二叉树为不为空，即数组为不为空，然后再建立根结点。
step 2：前序遍历第一个数字必定是根结点，然后我们就开始判断，在前序遍历中相邻的两个数字必定是只有两种情况：要么前序后一个是前一个的左节点、要么前序后一个是前一个的右节点或者其祖先的右节点。
step 3：同时顺序遍历pre和vin两个序列，判断是否是左结点，如果是左结点则不断向左深入，用栈记录祖先，如果不是需要弹出栈回到相应的祖先，然后进入右子树，整个过程类似非递归前序遍历。

具体重建过程可以参考如下图示： alt

代码实现:

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n = pre.size();
        int m = vin.size();
        if(n == 0 || m == 0) //每个遍历都不能为0
            return NULL;
        stack<TreeNode*> s;
        TreeNode *root = new TreeNode(pre[0]); //首先建立前序第一个即根节点
        TreeNode *cur = root;
        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;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，遍历一次数组，弹出栈的循环最多进行 $n$ 次
空间复杂度： $O (n)$ ，栈空间最大深度为 $n$