Leetcode--Java--106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

本题思路与中序前序建树几乎一模一样，

1. 注意根结点从末尾开始枚举，以及求右子树根结点位置时得细心点，画图不容易错。

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
       int n = postorder.length;
       return dfs(n - 1, 0, n - 1, inorder, postorder);
    }
    public TreeNode dfs(int r, int start, int end, int[] inorder, int[] postorder) {
        if (start > end) {
            return null;
        }
        int i = end;
        while ( i >= 0 && inorder[i] != postorder[r]) i --;
        TreeNode root = new TreeNode();
        root.val = postorder[r];
        //下一次左子树的根结点位置
        root.left = dfs(r - (end - i) - 1, start, i - 1, inorder, postorder);
        root.right = dfs(r - 1, i + 1, end, inorder, postorder);
        return root;
    }
}