Preorder inorder postorder

这三种tree traversal一定要记住，属于基本功。自己平时没事就练习一下，有助于打好基础
preorder: root, left, right
inorder: left root right
postorder: left right root

今天重新做了buildTree 系列，从inorder, postorder中buildTree。 从inorder, preorder 中buildtree。 还有从preorder, postorder中buildtree。这三种方式都遵循着一个思想，就是他们是从recursion 建立的数组，那么inorder 就必须left root right, postorder 就必须left right root, 那么postorder最后一个就是root，你用这个反过来建立tree就可以了，用inorder 作为参考，因为inorder最后一个是最右边的node，那么当你不断从右往左边走的时候，inorder 和postorder的数组的值就会相等，这时候你就走到最右边的node了，这时候返回，建立上一次递归时候node.right = 这次返回的node 的联系。之后只要当前root 不等于inorder的值，就继续node.left 的recursion，因为inorder 的值在中间会指向subtree的root，（别忘了inorder 是left, root, right， 所以你从左到右traverse的时候如果两个值相等，那么你就找到subtree的root了，这时候返回，如果不相等，那就继续recursion。这样递归就可以重新构建出一个tree了。

同样的道理，给你一个inorder, preorder数组，让你重建tree，那么这时候你就发现inorder 是left root right, preorder 是root left right, 你就要从root开始递归，所以用preorder来建立treenode， 然后用inorder来做参考，两个值相等的时候，你就找到了最左边，因为inorder是left root right, 你的两个指针都应该从0开始，不断增加。与postorder相反，因为postorder最右边才是root, 你从右边开始才能建立一个treenode， which is root。 主要思想就在从root开始，用递归的方法来重建一个tree，而你需要一个参考，这个参考数组就决定了你这个指针要从哪里开始。inorder 和postorder共同点就是他们从右往左能够找到最右边的treenode，而preorder 和inorder共同点就是他们能够找到最左边的treenode，所以从左往右开始递归。

最后一个相似的题就是给你preorder, postorder， 让你重建tree，preorder: root, left, right. postorder: left, right, root. 这时候你依然发现可以从左往右，preorder最左边就是root，所以用它来建立treenode，用postorder做参考，递归的时候就只传当前node就可以了，因为preorder是不断在建立left subtree，所以当preorder[i] == postorder[j] 的时候，你找到了最左边的treenode，然后返回，这时候返回的时候就是上一层的root，你要判断他有没有right leaf，这时候就看preorder[i] == postorder[j] 是否还相等，因为你上一层的时候已经更新了j指针，如果他们还相等，这时候这个node就是right Leaf。如此递归就可以重建一个tree出来了。

下面是这三题的代码

class buildTree_postorder {
    int inIndex, postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        inIndex = inorder.length - 1;
        postIndex = postorder.length - 1;
        return postBuildTree(inorder, postorder, null);
    }
    private TreeNode postBuildTree(int[] inorder, int[] postorder, TreeNode root) {
        if (postIndex < 0) {
            return null;
        }
        TreeNode n = new TreeNode(postorder[postIndex--]);
        // find rightest node
        // build the right subtree
        if (n.val != inorder[inIndex]) {
            n.right = buildTree(inorder, postorder, n);
        }
        inIndex--;
        if (root == null || root.val != inorder[inIndex]) {
            n.left = buildTree(inorder, postorder, root);
        }
        return n;
    }
}
class buildTree_preorder {
    int preIndex, inIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preIndex = 0;
        inIndex = 0;
        return buildTree(preorder, inorder, null);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, TreeNode root) {
        if (preIndex > preorder.length - 1) {
            return null;
        }
        TreeNode n = new TreeNode(preorder[preIndex++]);
        if (n.val != inorder[inIndex]) {
            n.left = buildTree(preorder, inorder, n);
        }
        inIndex++;
        if (root == null || root.val != inorder[inIndex]) {
            n.right = buildTree(preorder, inorder, root);
        }
        return n;
    }
}
class buildTree_prePostorder {
    int preIndex, postIndex;
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        preIndex = 0; postIndex = 0;
        return buildTree(pre, post, null);
    }
    private TreeNode buildTree(int[] pre, int[] post, TreeNode root) {
        if (preIndex > pre.length - 1) {
            return null;
        }
        TreeNode n = new TreeNode(pre[preIndex++]);
        if (n.val != post[postIndex]) {
            n.left = buildTree(pre, post, n);
        }
        if (n.val != post[postIndex]) {
            n.right = buildTree(pre, post, n);
        }
        postIndex++;
        return n;
    }
}