lintcode73. 前序遍历和中序遍历树构造二叉树

朴灿烈づ我的快乐病毒、 2023-07-03 06:27 22阅读 0赞

根据前序遍历和中序遍历树构造二叉树.

样例
    样例 1:
    
    输入：[],[]
    输出：{
        }
    解释：
    二叉树为空
    样例 2:
    
    输入：[2,1,3],[1,2,3]
    输出：{
        2,1,3}
    解释：
    二叉树如下
      2
     / \
    1   3
    注意事项
    你可以假设树中不存在相同数值的节点

/**
     * Definition of TreeNode:
     * class TreeNode {
     * public:
     *     int val;
     *     TreeNode *left, *right;
     *     TreeNode(int val) {
     *         this->val = val;
     *         this->left = this->right = NULL;
     *     }
     * }
     */
    
    class Solution {
        
    public:
        /**
         *@param preorder : A list of integers that preorder traversal of a tree
         *@param inorder : A list of integers that inorder traversal of a tree
         *@return : Root of a tree
         */
        TreeNode * buildTree(vector<int> &preorder, vector<int> &inorder) {
        
            // write your code here
            map<int,int> index;
            for (int i = 0; i < inorder.size(); i++) {
        
                /* code */
                index[inorder[i]]=i;
            }
            return building(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1,index);
        }
        TreeNode* building(vector<int> &preorder, vector<int> &inorder,int prestart, int preend ,int instart,int inend,map<int,int>index)
        {
        
            if(prestart>preend||instart>inend) return NULL;
            int i=index[preorder[prestart]];
            int len=i-instart;
            TreeNode*newroot=new TreeNode(preorder[prestart]);
            newroot->left=building(preorder,inorder,prestart+1,prestart+len,instart,i-1,index);
            newroot->right=building(preorder,inorder,prestart+len+1,preend,i+1,inend,index);
            return newroot;
        }
    };