Java~二叉树进阶练习题：根据先序遍历和中序遍历构建二叉树 与 根据后序遍历和中序遍历构建二叉树

首先我们要明白先中后序遍历的特点：

• 先序遍历中 第一个一定是根结点。
• 中序遍历中 根结点左子树的所有结点一定在根结点的左边，右子树的所有结点一定在根结点的右边。所有中序遍历的序列组成可以表示为 ：左子树结点+根结点+右子树结点。
• 后序遍历中 最后一个结点一定是根结点。**

根据先序遍历和中序遍历构建二叉树
解题细想：

代码如下：

//根据一棵树的前序遍历与中序遍历构造二叉树。
class Solution {
    private int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        index = 0;
        return myBuildTree(preorder, inorder, 0, preorder.length);
    }
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int indexLeft, int indexRight) {
        if(indexLeft >= indexRight) {
            return null;
        }
        if(index >= inorder.length) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[index]);
        index ++;
        int pos = findNodePos(inorder, node.val);
        node.left = myBuildTree(preorder, inorder, indexLeft, pos);
        node.right = myBuildTree(preorder, inorder, pos + 1, indexRight);
        return node;
    }

    private int findNodePos(int[] inorder, int val) {
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return  -1;
    }
}

根据后序遍历和中序遍历构建二叉树：
解题思想：

1. 只要把上面的题回了，这道题很简单的。
2. 首先后序遍历的最后一个结点是根结点，所以一开始index=数组的长度-1.
3. 上面那道题是先建立左子树，再建立右子树，而这道题是后序遍历，所以要先建立右子树，再建立左子树。
4. 其他递归条件和上一道题一样。

class Solution {
    private int index = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index = postorder.length - 1;
        return myBuildTree(inorder, postorder, 0, postorder.length);
    }

    public TreeNode myBuildTree(int[] inorder, int[] postorder, int indexLeft, int indexRight) {
        if(indexLeft >= indexRight) {
            return null;
        }
        if(index < 0) {
            return null;
        }
        TreeNode node = new TreeNode(postorder[index]);
        index --;
        int pos = findNodePos(inorder, node.val);
        node.right = myBuildTree(inorder, postorder, pos + 1, indexRight);
        node.left = myBuildTree(inorder, postorder, indexLeft, pos);
        return node;
    }
    private int findNodePos(int[] inorder, int val) {
        for(int i = 0; i < inorder.length; i ++) {
            if(inorder[i] == val) {
                return i;
            }   
        }
        return -1;
    }
}