[leetCode106] 从中序和后序遍历构造树

原理就是，每次从后续遍历的尾部取出一个元素，以这个元素为分割点， 将中序和后序序列分为两边，再分别在两边里面做递归 代码容易出错，所以最好加上调试语句，方便找错

public class Solution {
          
   

    public TreeNode buildTree(int[] inorder, int[] postorder) {
          
   
        TreeNode root = new TreeNode();
        if (inorder.length == 0) return root;
        root=traversal(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
        return root;
    }

    public TreeNode traversal(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
          
   
        if (postLeft > postRight || inLeft > inRight) return null;
        int val=postorder[postRight];
        System.out.println("val:"+val);
        System.out.println("inleft:"+inLeft+"   inright:"+inRight+"     postleft:"+postLeft+"   postright:"+postRight);
        TreeNode root=new TreeNode(val);
        if (postLeft == postRight || inLeft == inRight) return root;
        int inPtr;
        for ( inPtr=inLeft;inPtr<inRight;inPtr++){
          
   
            if (inorder[inPtr]==val)    break;
        }
        
        int num=inPtr-inLeft;
        int postPtr=postLeft+num;
        
        System.out.println("inptr:"+inPtr+"   postPtr"+postPtr);
        System.out.println("-------------");
        System.out.println("inorder left:");
        for (int i=inLeft;i<=inPtr-1;i++)
            System.out.println(inorder[i]);
        System.out.println("inorder right:");
        for (int i=inPtr+1;i<=inRight;i++)
            System.out.println(inorder[i]);
        System.out.println("postorder left");
        for (int i=postLeft;i<=postPtr-1;i++)
            System.out.println(postorder[i]);
        System.out.println("postorder right");
        for (int i=postPtr;i<=postRight-1;i++)
            System.out.println(postorder[i]);

        TreeNode leftNode=traversal(inorder,inLeft,inPtr-1,postorder,postLeft,postPtr-1);
        TreeNode rightNode=traversal(inorder,inPtr+1,inRight,postorder,postPtr,postRight-1);

        root.left=leftNode;
        root.right=rightNode;
        return root;
    }
}