题解 | #重建二叉树#

前提知识：
前序遍历 ： 节点按照[ 根 | 左 | 右 ] 顺序遍历
中序遍历： 节点按照[ 左 | 根 |右 ] 顺序遍历
由此可知：
1.前序遍历的首元素为树的根节点值。
2.根节点的值可以将中序遍历划分为 [左子树中序遍历 | 根节点 | 右子树中序遍历 ]。
3.根据中序遍历左右子树的节点个数，可以将前序遍历划分为 [根节点 | 左子树前序遍历 | 右子树前序遍历 ]

题解一：递归
题解思路： 通过上述分析，可以递归的处理所有子树
递归分析：
1.递归参数： pre前序遍历数组， vin 中序遍历数组， left中序遍历左边界，right中序遍历右边界
2. 递归边界： left>right 返回NULL
3.回溯返回 root
并且为了降低查询根节点在中序中索引的时间复杂度，我们利用哈希表快速定位。
图示：

复杂度分析：
时间复杂度：，N节点个数
空间复杂度：，使用O(N）空间存储哈希映射。其次，递归栈深度最优O(logN)此时二叉树为满二叉树；最坏O(N):树退化为链表

实现如下：

class Solution {
public:
    unordered_map<int, int> mp;
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        for(int i = 0;i<vin.size();i++) mp[vin[i]] = i;
        return recovery(pre, vin, 0, vin.size()-1);
    }
    TreeNode* recovery(vector<int> &pre,vector<int> vin,int left,int right){
        if(right<left) return NULL;// 递归终止
        TreeNode* root = new TreeNode(pre[0]);// 建立根节点
        pre.erase(pre.begin());// 删除前序的首元素
        int mid = mp[root->val];// 根节点在中序遍历的索引值
        root->left = recovery(pre, vin, left, mid-1);//递归左子树
        root->right = recovery(pre,vin,mid+1,right);//递归右子树
        return root;
    }
};

前提： 前序遍历相邻两个值a,b之间的关系
1：a有左子树，那么b就是a的直接左儿子；
2: a没有左子树但是有右子树，b为a的右儿子； a为叶子节点，那么b为a祖先节点的右儿子；
图示：
情况1：

情况2：

题解二：迭代(利用辅助栈)
题解思路：
1.根据上述分析的关系，我们使用栈保存祖先节点和指针inorder来遍历中序遍历数组。
2. 我们一次枚举前序遍历中除了第一个节点外的每个节点。 如果indorder等于栈顶元素，那么就不断地弹出栈顶元素并移动inorder, 并将当前节点作为最后一个弹出的节点的右儿子;如果不同，那么就将当前节点作为栈顶节点的左儿子；
复杂度分析：
时间复杂度：
空间复杂度：

实现如下：

class Solution {
public:
     TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()==0) return NULL; //判空
        stack<TreeNode*> st;
        TreeNode* root = new TreeNode(pre[0]); //创建根节点
        st.push(root); //根节点入栈
        int inorder = 0;
        //遍历前序遍历
        for(int i = 1;i<pre.size();i++)
        {
            TreeNode * node = st.top(); //获取栈顶
            if(node->val != vin[inorder])
            {
                //如果不同，那么就将当前节点作为栈顶节点的左儿子
                node->left = new TreeNode(pre[i]);
                st.push(node->left);
            }
            else{
                //如果相等，则前序遍历中的左子树所有节点已经入栈
                //根据中序遍历，对左子树上节点的重建
                while(!st.empty() && st.top()->val == vin[inorder])
                {
                    node = st.top();
                    st.pop();
                    inorder++;
                }
                //当前节点作为最后一个弹出的节点的右儿子
                node->right = new TreeNode(pre[i]);
                st.push(node->right);
            }
        }
    return root;
    }
};

此题同NC12