lintcode 72. 中序遍历和后序遍历树构造二叉树

电玩女神 2023-07-03 07:10 1阅读 0赞

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

样例
    样例 1:
    
    输入：[],[]
    输出：{
        }
    解释：
    二叉树为空
    样例 2:
    
    输入：[1,2,3],[1,3,2]
    输出：{
        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 inorder: A list of integers that inorder traversal of a tree
         * @param postorder: A list of integers that postorder traversal of a tree
         * @return: Root of a tree
         */
        TreeNode * buildTree(vector<int> &inorder, vector<int> &postorder) {
        
            // write your code here
           for (int i = 0; i < inorder.size(); i++) {
        
               /* code */
               index[inorder[i]]=i;
           }
           return building(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
        }
        TreeNode*building(vector<int> &inorder, vector<int> &postorder,int instart,int inend,int poststart,int postend)
        {
        
            if(instart>inend||poststart>postend) return NULL;
            int val=postorder[postend];
            int i=index[val];
            TreeNode*newhead=new TreeNode(val);
            int leftnum=i-instart;
            newhead->left=building(inorder,postorder,instart,i-1,poststart,poststart+leftnum-1);
            newhead->right=building(inorder,postorder,i+1,inend,poststart+leftnum,postend-1);
            return newhead;
        }
        map<int,int> index;
    };