题目：106. 从中序与后序遍历序列构造二叉树

思路：深度优先搜索dfs，时间复杂度0(n^2)。
后续遍历的最后一个节点就是当前子树的根节点，遍历中序遍历，找到根节点，那其左边的就是左子树，右边的就是右子树，细节看注释。

C++版本：

/**
 * 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:
    TreeNode * dfs(vector<int>& inorder, vector<int>& postorder,int a,int b,int c,int d){
        if(a>b) return nullptr;
        // 遍历中序遍历，找到根节点
        for(int i=a;i<=b;i++){
       		// 后续遍历的最后一个节点就是当前子树的根节点
            if(inorder[i]==postorder[d]){
                TreeNode * tmp=new TreeNode(inorder[i]);
                // 中序遍历左边的就是左子树
                tmp->left= dfs(inorder,postorder,a,i-1,c,c+i-a-1);
                // 中序遍历右边的就是右子树
                tmp->right=dfs(inorder,postorder,i+1,b,c+i-a,d-1);
                return tmp;
            }
        }
        return nullptr;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return dfs(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
    }
};

JAVA版本：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode dfs(int[] inorder, int[] postorder,int a,int b,int c,int d){
        if(a>b) return null;
        for(int i=a;i<=b;i++){
            if(inorder[i]==postorder[d]){
                TreeNode tmp=new TreeNode(inorder[i]);
                tmp.left= dfs(inorder,postorder,a,i-1,c,c+i-a-1);
                tmp.right=dfs(inorder,postorder,i+1,b,c+i-a,d-1);
                return tmp;
            }
        }
        return null;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return dfs(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
    }
}

GO版本：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    return dfs(inorder,postorder,0,len(inorder)-1,0,len(postorder)-1)
}
func dfs(inorder []int, postorder []int,a,b,c,d int) *TreeNode {
    for i:=a;i<=b;i++ {
        if inorder[i]==postorder[d] {
            tmp:=&TreeNode{Val:postorder[d]}
            tmp.Left=dfs(inorder,postorder,a,i-1,c,c+i-a-1);
            tmp.Right=dfs(inorder,postorder,i+1,b,c+i-a,d-1);
            return tmp
        }
    }
    return nil
}