ORID47 复习pre,in,postOrder traversal

刷两道题 √
学习一章Android project的课程

今天写了leetcode每日一题还有一道来自这个网站的每日一题
今天读了这篇文章我觉得对于刷题还是很有帮助的，因为学习就是不断地重复，这是最基本的方法。
早上到了酒店就开始看今天的每日一题，我觉得这样养成习惯也挺好，因为这样保证了我每天至少能够2道题。
inorder, preorder, postorder 其实也挺好记的，就是你把root看作中心，INORDER 就是说按着正常来（也就是中心就是root）也就是LEFT, ROOT, RIGHT
而pre的意思就是说把中心放到了最前面，所以是ROOT, LEFT, RIGHT
而post就是说把中心放到了最后面，所以是LEFT,RIGHT,ROOT

Construct Binary Tree from Inorder and Postorder Traversal

这道题就是给你两个数组，一个是Inorder traversal，一个是postorder，我之前做过类似的题目，但是还是想不出来，所以参考了自己以前的答案。不过我出发点是没有问题的，就是你要从post最后开始，因为那里是root，这种类型的题目（指的是construct binary tree的题目）主要就是要先找到root，而inorder是没法找到root的，因为你不知道它具体在哪里。
所以要从post开始，然后查找和inorder有没有重合，因为题目里面说了两组数里面没有相同的数（或者说整个二叉树里面没有相同数值得数）
如果相等的话，那么inorderIndex--，不是的话，postorder--
然后用递归的形式继续把它传下去，因为postorder是left right root，而你是从最右边往左边走，所以你先架构的就是二叉树的整个右半边的部分。所以递归的时候应该是
root.right = buildTree(inorder, postorder, root);
如果相等了，那么证明你找到了root，也就是说从这开始，你要构建二叉树的左半边了，所以
root.left = buildTree(inorder, postorder, root);
下面是代码

代码实现

    int inIndex, postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        inIndex = inorder.length - 1;
        postIndex =  postorder.length - 1;
        
        return buildTree(inorder, postorder, null);
    }
    private TreeNode buildTree(int[] inorder, int[] postorder, TreeNode root) {
        if (postIndex < 0) {
            return null;
        }
        // init root 
        TreeNode n = new TreeNode(postorder[postIndex--]);
        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;
    }