剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

限制：

0 <= 节点个数 <= 5000

递归

前序遍历中，第一个数字是二叉树的根节点

中序遍历中，根节点的左侧是左子树的节点，根节点的右侧是右子树的节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //递归出口
        if(preorder.empty() || inorder.empty())
            return NULL;  
        //建立二叉树
        TreeNode *head = new TreeNode;
        head->val = preorder[0];
        //找到根节点的位置
        int root = 0;
        for(int i=0;i<preorder.size();i++){
            if(preorder[0]==inorder[i]){
                root = i;
                break;
            }
        }
        // 先序遍历和中序遍历的左右子树vector
        vector<int> left_pre,left_in,right_pre,right_in;
        for(int i=0;i<root;i++){
            left_pre.push_back(preorder[i+1]);
            left_in.push_back(inorder[i]);
        }
        for(int i=root+1;i<preorder.size();i++){
            right_pre.push_back(preorder[i]);
            right_in.push_back(inorder[i]);
        }

         // 根节点的左右节点
        head->left = buildTree(left_pre,left_in);
        head->right = buildTree(right_pre,right_in);
        return head;
    }
};

改进：
中序序列可以使用哈希表存储，便于查找根节点，参数传入可以为前序,中序，前序序列根节点，中序序列左边界，中序序列右边界

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int> map;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 将中序序列用哈希表存储，便于查找根节点
        for(int i = 0;i < inorder.size();i++)
            map[inorder[i]] = i;
        // 传入参数：前序,中序，前序序列根节点，中序序列左边界，中序序列右边界
        return build(preorder,inorder,0,0,inorder.size()-1);
    }
    TreeNode* build(vector<int>& preorder, vector<int>& inorder,int pre_root,int in_left,int in_right){
        if(in_left > in_right)
            return NULL;
        TreeNode* root = new TreeNode(preorder[pre_root]);
        // 根节点在中序序列中的位置，用于划分左右子树的边界
        int in_root = map[preorder[pre_root]];
        // 左子树在前序中的根节点位于：pre_root+1,左子树在中序中的边界：[in_left,in_root-1]
        root->left = build(preorder,inorder,pre_root+1,in_left,in_root-1);
        // 右子树在前序中的根节点位于：根节点+左子树长度+1 = pre_root+in_root-in_left+1
        // 右子树在中序中的边界：[in_root+1,in_right]
        root->right = build(preorder,inorder,pre_root+in_root-in_left+1,in_root+1,in_right);
        return root;
    }
};

迭代

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()) return nullptr;
        stack<TreeNode*> s;
        TreeNode *root=new TreeNode(preorder[0]);  //根节点
        TreeNode *cur=root;  //正在确定位置的节点
        for(int i=1,j=0;i<preorder.size();i++) {
            //有左子树的情况，一直沿左子树深入，并将沿途节点放入栈中
            if (cur->val != inorder[j]) {  //inorder[j]代表最左节点（去除已经确定左子树的节点）
                cur->left = new TreeNode(preorder[i]);
                s.emplace(cur);
                cur = cur->left;
            } else {  //没有左子树的情况
                j++;
                while (!s.empty() && s.top()->val == inorder[j]) {  //栈顶是其父节点，判断有无右子树
                    cur = s.top();  //没有右子树，就追溯到有右节点的祖父节点
                    s.pop();
                    j++;
                }
            cur = cur->right = new TreeNode(preorder[i]);  //preorder[i]即当前节点的右子树节点，并且下次从右子树开始遍历
            }
        }
        return root;
    }
};