106. 从中序与后序遍历序列构造二叉树

一 题目：

二 思路：

-后序遍历的数组最后一个节点是根节点，找到根节点在中序遍历的位置，可以划分为左右子树。

• eg:
  • 1 2 4 ,5,2,3,1
  • 1 2 4 ,2,3,1,5

三 代码：

 public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length==0){
            return null;
        }
        int rootVal = postorder[postorder.length - 1];
        //本结点构造
        TreeNode curr=new TreeNode(rootVal);
        int rootIndex=-1;
        //找到根在中序遍历的位置
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i]==rootVal){
                rootIndex=i;
                break;
            }
        }
        curr.left=buildTree(Arrays.copyOfRange(inorder,0,rootIndex),Arrays.copyOfRange(postorder,0,rootIndex));

        curr.right=buildTree(Arrays.copyOfRange(inorder,rootIndex+1,inorder.length),Arrays.copyOfRange(postorder,rootIndex,inorder.length-1));
        return curr;
    }

再来个先序和中序

  public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length==0){
            return null;
        }
        int rootVal = preorder[0];
        TreeNode curr=new TreeNode(rootVal);
        int rootIndex=-1;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i]==rootVal){
                rootIndex=i;
                break;
            }
        }
        curr.left=buildTree(Arrays.copyOfRange(preorder,1,rootIndex+1),Arrays.copyOfRange(inorder,0,rootIndex));
        curr.right=buildTree(Arrays.copyOfRange(preorder,rootIndex+1,preorder.length),Arrays.copyOfRange(inorder,rootIndex+1,inorder.length));
        return curr;
    }