algorithm - 如何检查给定的前序、中序和后序遍历是否属于同一二叉树？

Question

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

但是代码似乎给出了运行时错误! 我正在检查是否可以通过 bool 值进行中序和先序遍历来创建一棵树。

我构建树的代码如下

    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

问题说“检查给定的前序、中序和后序遍历是否属于同一二叉树？”。 您正在根据中序和前序创建一棵树，然后使用给定的后序检查其后序遍历。在这里，您假设中序和预序将始终位于同一棵树中。这不一定是真的。 inoder 和 postorder 可能属于同一棵树，而 preorder 可能属于不同树。因此，您的代码会出现运行时错误。

如何解决这个问题: 如果给出了 inorder & preorder 或 inorder & postorder 则可以创建一棵树。 检查下面 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;

public class Test {
    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);
    }

}