java - 根据中序和后序创建一棵树

Question

只是为了好玩，我正在尝试创建 at tree out of inorder 和 postorder，我知道网上有很多解决方案，但我是自己做的，感觉我很接近，这是我的代码:

根据当前输入，我期望树

     7
   5    10
4   6  8  11

但我得到的是

    7
   5    10
4   6  11  11

public static TreeNode buildTreeHelper(int[] inorder, int[] postorder, int inOrderIndex, int end){
        if(end<0 || inOrderIndex<0){
            return null;
        }
        TreeNode root = new TreeNode(postorder[end]);
        int index = search(inorder,inOrderIndex,end,root.val);
        if(index!=-1){
            root.left = buildTreeHelper(inorder, postorder,inOrderIndex,index-1);
            root.right= buildTreeHelper(inorder, postorder,index+1,end-1);
        }
        return root;
    }

    public  static int search(int[]inorder, int start, int end, int target){
        for(int i=start; i<=end; i++){
            if(inorder[i]==target){
                return i;
            }
        }
        return -1;
    }    
    public static void main(String[] args){
        int[] inorder = {4, 5, 6, 7, 8, 10, 11};
        int[] postorder = {4, 6, 5, 8, 11, 10, 7};
        TreeNode ret = buildTreeHelper(inorder, postorder, 0, inorder.length-1);

    }

Answer 1

在我看来，您的 inOrderIndex 和 end 参数可以变成 inOrderIndex > end。所以我会检查这个逻辑。我会调试以查看您在哪个点上缺少值 8 并改用 10。