【Leetcode】106. Construct Binary Tree from Inorder and Postorder Traversal（中序和后序求解二叉树）

浅浅的花香味﹌ 2022-02-16 21:25 142阅读 0赞

Given inorder and postorder traversal of a tree, construct the binary tree.

**Note:**  
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
    postorder = [9,15,7,20,3]

Return the following binary tree:

3
       / \
      9  20
        /  \
       15   7

题目大意：

根据已给出的二叉树中序和后序遍历求解二叉树的结构。

解题思路：

/**
     * 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 {
    private:
        unordered_map<int, int> inm;
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            int n = inorder.size(), i=0;
            for(auto val: inorder) inm[val] = i++;
            
            return dfs(inorder, 0, n-1, postorder, 0, n-1);
        }
        
        
        TreeNode* dfs(vector<int>& inorder, int ileft, int iright, vector<int>& postorder, int pleft, int pright){
            
            if(ileft>iright) return nullptr;
            
            int val = postorder[pright];
            TreeNode *root = new TreeNode(val);
            
            if(ileft == iright) return root;
            
            int iroot = inm[val];
            
            int nleft = iroot -ileft;
            
            root->right = dfs(inorder, iroot+1, iright, postorder, pleft+nleft, pright-1);
            root->left = dfs(inorder, ileft, iroot-1, postorder, pleft, pleft+nleft -1);
            
            return root;
            
        }
    };