BM40. [重建二叉树]

alt

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM40. 重建二叉树

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=295&sfm=github&channel=nowcoder

题目的主要信息：

根据二叉树的前序遍历序列和中序遍历序列，重建该二叉树，并返回根节点
两个遍历都没有重复的元素

方法一：递归
具体做法：
对于二叉树的前序遍历，我们知道序列的第一个元素必定是根节点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根节点将二叉树分成了左右子树两个部分，如下图所示：
图片说明

我们可以发现，数字1是根节点，并将二叉树分成了(247)和(3568)两棵子树，而子树的的根也是相应前序序列的首位，比如左子树的根是数字2，右子树的根是数字3，这样我们就可以利用前序遍历序列找子树的根节点，利用中序遍历序列区分每个子树的节点数。
我们可以递归解决，先建立根节点，然后遍历中序遍历找到根节点在数组中的位置，然后按照子树的节点数将两个遍历的序列分割成子数组，将子数组送入函数建立子树。

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;
        TreeNode *root = new TreeNode(pre[0]);
        for(int i = 0; i < vin.size(); i++){
            if(pre[0] == vin[i]){ //找到中序遍历中的前序第一个元素
                vector<int> leftpre(pre.begin() + 1, pre.begin() + i + 1);  //左子树的前序遍历
                vector<int> leftvin(vin.begin(), vin.begin() + i); //左子树的中序遍历
                root->left = reConstructBinaryTree(leftpre, leftvin); //构建左子树
                vector<int> rightpre(pre.begin() + i + 1, pre.end()); //右子树的前序遍历
                vector<int> rightvin(vin.begin() + i + 1, vin.end()); //右子树的中序遍历
                root->right = reConstructBinaryTree(rightpre, rightvin); //构建右子树
                break;
            }
        }
        return root;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，构建每个节点进一次递归，递归中所有的循环加起来一共 $n$ 次
空间复杂度： $O(n)$ ，递归栈最大深度不超过 $n$ ，辅助数组长度也不超过 $n$

方法二：栈
具体做法：
我们可以用类似非递归先序遍历的方式建立二叉树。
首先前序遍历第一个数字依然是根节点，然后我们就开始判断，在前序遍历中相邻的两个数字必定是只有两种情况：

要么先序后一个是前一个的左节点
要么先序后一个是前一个的右节点或者其祖先的右节点

我们可以同时顺序遍历pre和vin两个序列，判断是否是左节点，如果是不断向左深入，用栈记录祖先，如果不是需要弹出栈回到相应的祖先，然后进入右子树，整个过程类似非递归前序遍历。
图片说明

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;
    }
};

复杂度分析：