从中序与后序序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这棵 二叉树 。

示例

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

输出：[3,9,20,null,null,15,7]

思路

首先能明确后序遍历序列的最后一个必定是二叉树的根节点。

如示例，3就是二叉树的根节点，然后根据中序遍历的特点，可以知道3的左孩子必定在中序遍历序列中3的左边，3的右孩子必定在中序遍历序列中3的右边。所以可以在中序遍历序列中从3的位置将序列分为两部分序列，根据这两部分序列长度也可以将后序遍历序列分为两部分，也就是如下的概念图：

因为左孩子序列只有9一个，所以9就是3的左孩子节点；而右孩子序列我们可以单独作为一棵二叉树来进行分析。

20肯定是根节点，左孩子是15，右孩子是7。

将其拼接到上面的树中即可得到完整的二叉树。

可以看出解决这个问题的关键在于分层切割，在每一层都分割后序和中序遍历序列，所以可以使用递归，在递归的每一层我们要解决这些问题：

1. 如果后序序列没有元素，则直接结束
2. 如果后序序列只有一个元素，则将其添加成为节点，然后结束
3. 如果后序序列有多个元素，则将最后一个添加成为节点
4. 然后用此元素切割中序序列切为左中序序列和右中序序列
5. 用切割后的两个序列长度切割后序序列切为左后序序列和右后序序列
6. 然后进行下一层的递归，下一层递归要分左右，并且明确指定下一层要添加的是左孩子还是右孩子

实现代码

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode root=new TreeNode();
        traversal(inorder,postorder,0,inorder.length,0,postorder.length,root,true);
        return root.left;
    }

    public void traversal(int[] inorder,int[] postorder,int inStart,int inEnd,int postStart,int postEnd,TreeNode father,boolean isLeft) {
        //后序序列长度为0
        if(postStart==postEnd)
            return;
        //后序序列最后一个
        int postLast=postorder[postEnd-1];
        TreeNode node;
        if(isLeft) {
            father.left=new TreeNode(postLast);
            node=father.left;
        } else {
            father.right=new TreeNode(postLast);
            node=father.right;
        }
        //后序序列长度为1，没必要再对两个长度为0的序列进行处理
        if(postEnd-postStart==1)
            return;
        //在中序序列中查找后序序列的最后一个
        int index=inStart;
        for(int i=inStart;i<inEnd;i++) {
            if(postLast==inorder[i]) {
                index=i;
                break;
            }
        }
        traversal(inorder,postorder,inStart,index,postStart,postStart+index-inStart,node,true);
        traversal(inorder,postorder,index+1,inEnd,postStart+index-inStart,postEnd-1,node,false);
    }

}

同样的方法我们可以根据前序序列和中序序列构造二叉树，只要每次从前序序列最前取节点并分割序列就行了。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root=new TreeNode();
        traversal(inorder,preorder,0,inorder.length,0,preorder.length,root,true);
        return root.left;
    }

    public void traversal(int[] inorder, int[] preorder, int inStart, int inEnd, int preStart, int preEnd, TreeNode father, boolean isLeft) {
        if(preStart==preEnd)
            return;
        int preFirst=preorder[preStart];
        TreeNode node;
        if(isLeft) {
            father.left=new TreeNode(preFirst);
            node=father.left;
        } else {
            father.right=new TreeNode(preFirst);
            node=father.right;
        }
        if(preEnd-preStart==1)
            return;
        int index=inStart;
        for(int i=inStart;i<inEnd;i++) {
            if(preFirst==inorder[i]) {
                index=i;
                break;
            }
        }
        traversal(inorder,preorder,inStart,index,preStart+1,preStart+1+index-inStart,node,true);
        traversal(inorder,preorder,index+1,inEnd,preStart+1+index-inStart,preEnd,node,false);
    }
}