在inorder和postorder之外创建一个树

Question

只是为了好玩，我试着在树上创建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。

Answer 2

以下是解决问题的建议步骤：

1. 后序数组的最后一个元素是根；
2. 在有序树中找到根的索引，左tree;
3. Calculate的长度，有序和后序arrays;
4. Recursively的起始索引和结束索引，求解左树和右树

在您构建右树的解决方案中，有序数组的起始索引等于后序数组的起始索引，这是不正确的。例如，在第一次迭代中，根是7，in-order的索引是3，右侧树的in-order数组的起始索引是4，其中存储值8，但post-order的起始索引是3，其中存储的值是8。因此，您需要分别为in-order和post-order创建索引。

解决方案将如下所示

public static TreeNode buildTreeHelper(int[] inorder, int[] postorder,
    int inOrderStart, int inOrderEnd, int postOrderStart, int postOrderEnd) {
        if (inOrderEnd < 0 || inOrderStart < 0 || postOrderEnd < 0
                || postOrderStart < 0) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postOrderEnd]);

        // special case: when the node is a leaf
        if (inOrderStart == inOrderEnd) {
            return root;
        }

        int index = search(inorder, inOrderStart, inOrderEnd, root.val);
        if (index != -1) {

            //get the length of the left tree
            int leftTreeLen = index - inOrderStart; 

            root.left = buildTreeHelper(inorder, postorder, inOrderStart,
                    index - 1, postOrderStart, postOrderStart + leftTreeLen - 1);
            root.right = buildTreeHelper(inorder, postorder, index + 1,
                    inOrderEnd, postOrderStart + leftTreeLen, postOrderEnd - 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, 0, postorder.length - 1);

}