如何检查给定的前序，后序和后序遍历是否在同一二叉树中？

Question

[目前，我有以下算法尝试根据给定的有序和预遍历遍历创建树，并检查树的后序遍历以使用给定的后序构建？

但是代码似乎给运行时错误！我正在检查是否甚至可以通过布尔来进行有序遍历和预遍历遍历。

我构建树的代码如下

    static TreeNode buildTree(int start,int end,int root_pos)
    {
        if(start>end)
            return null;

        int key=preorder.get(root_pos);
        TreeNode root=new TreeNode(key);

        int i=start;
        for(;i<=end;i++)
        {
            if(inorder.get(i)==key)
                break;
        }

        if(i>end) //Case when we couldn't find root in given inorder
        {
            possible=false; //this tree cannot be made from given inorder and preorder traversals
            return null;
        }
        else
        {
            root.left=buildTree(start, i-1, root_pos+1);
            root.right=buildTree(i+1, end, root_pos+i-start+1);
            return root;

        }

    }

我想念什么情况？该怎么办？

我知道如何根据有效的遍历构造树，我想知道给定的遍历（可能无效）是否属于同一棵树？

完整的问题说明给出here.

Answer 1

问题说：“检查给定的预遍历，有序遍历和后遍历遍历是否属于相同的二叉树？”。您正在根据有序和预购创建树，然后使用给定的后购检查其后购遍历。在这里，您假设顺序和预顺序始终是同一棵树。这不一定是正确的。序号和后序可能是同一棵树，而预序可能是不同的树。因此，您的代码出现运行时错误。

如何解决此问题：如果给出了订单和预购订单或订单和后订单，则可以创建树。检查下面https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/https://www.geeksforgeeks.org/construct-a-binary-tree-from-postorder-and-inorder/

现在，对于当前问题，我们要做的是遍历两棵树创建过程中的树形成逻辑，并查看我们是否在每一步以相同的值降落在节点上。如果在任何步骤我们遇到不同的值，则意味着有序，前序或后序遍历之一不正确。如果有帮助，请粘贴下面的代码以进行检查]

import java.util.HashMap;

import java.util.Map;

公开课测试{int res;

public static void main(String[] args) {
    Test test = new Test();

    int[] pre = {1, 5, 4, 2, 3};
    int[] in = {4, 2, 5, 1, 3};
    int[] post = {4, 1, 2, 3, 5};

    int res = test.solve(pre, in, post);
    System.out.print(res);
}


public int solve(int[] A, int[] B, int[] C) {
    if (A.length != B.length || B.length != C.length)
        return 0;

    res = 1;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < B.length; i++)
        map.put(B[i], i);

    util(A, map, C, 0, B.length - 1, 0, C.length - 1);
    return res;
}

private void util(int[] pre, Map<Integer, Integer> map, int[] post, int inStart, int inEnd, int preIndex, int postIndex) {
    if (inStart > inEnd)
        return;

    Integer mid = map.get(pre[preIndex]);
    if (mid == null || pre[preIndex] != post[postIndex]) {
        res = 0;
        return;
    }

    // check for left part of tree
    util(pre, map, post, inStart, mid - 1, preIndex + 1, postIndex - (inEnd - mid) - 1);

    // check for right part of tree
    util(pre, map, post, mid + 1, inEnd, preIndex + (mid - inStart) + 1, postIndex - 1);
}

}