leetcode105. 从前序与中序遍历序列构造二叉树

分析

前序遍历中可以找出中序遍历的根节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int>map;
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder,
        int pl,int pr,int il,int ir){
            if(pl>pr)return nullptr;
            //前序的第一个就是中序的根节点
            int pre_root=pl;
            //在map找到中序的位置
            int in_root=map[preorder[pre_root]];
            //建立根节点
            TreeNode*root=new TreeNode(preorder[pre_root]);
            //左子树的数量=中序遍历的根节点-中序的左端点
            int size_left=in_root-il;
            //创建左子树，前序区间：从前序左端点+1开始，共size_left个节点
            //创建左子树，中序区间：从中序的右端点开始，到中序根节点前一个节点结束
            root->left=myBuildTree(preorder,inorder,pl+1,pl+size_left,il,in_root-1);
            //创建右子树，前序区间：从前序区间+size_left+1开始，到前序右端点pl结束
             //创建右子树，中序区间：从中序区间根节点+1开始，到中序右端点il结束
            root->right=myBuildTree(preorder,inorder,pl+size_left+1,pr,in_root+1,ir);
            return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n=preorder.size();
        for(int i=0;i<inorder.size();i++)map[inorder[i]]=i;
        return myBuildTree(preorder,inorder,0,n-1,0,n-1);
    }
};