等效排序二叉树Java

Question

我正在学习Go，在本教程中，可以使用并发和通道来完成这个练习：解决方案。

我试图通过Java解决这个问题。我能想到的解决方案是使用临时数据结构来存储顺序遍历这两棵树的结果，然后进行比较。

例如，我使用StringBuilder存储顺序遍历的结果，然后进行比较（注意，我们正在比较排序的二叉树）：

    public boolean equivalentBST(TreeNode p, TreeNode q) {
        StringBuilder pSb = new StringBuilder();
        walk(pSb, p);
        StringBuilder qSb = new StringBuilder();
        walk(qSb, q);
        return pSb.compareTo(qSb) == 0;
    }

    private void walk(StringBuilder sb, TreeNode node) {
        if (node == null) {
            return;
        }
        walk(sb, node.left);
        sb.append(node.val);
        walk(sb, node.right);
    }

测试用例：

        TreeNode p = new TreeNode(9);
        TreeNode p2 = new TreeNode(8);
        TreeNode p3 = new TreeNode(7);
        p.left = p2;
        p2.left = p3;

        TreeNode q = new TreeNode(9);
        TreeNode q2 = new TreeNode(8);
        TreeNode q3 = new TreeNode(7);
        q3.right = q2;
        q.left = q3;

        System.out.println(equivalentBST(q, p)); // output true

我想知道有没有其他更好的方法通过Java解决这个问题？

Answer 1

您可以同时遍历这两棵树并立即比较它们的元素，而无需使用StringBuilder。

大致意思是：

public boolean equivalentBST(TreeNode node1, TreeNode node2) {
    var stack1 = new ArrayList<TreeNode>();
    var stack2 = new ArrayList<TreeNode>();

    while (true) {
        while (node1 != null) {
            stack1.add(node1);
            node1 = node1.left;
        }
        while (node2 != null) {
            stack2.add(node2);
            node2 = node2.left;
        }
        if (stack1.isEmpty() || stack2.isEmpty())
            return stack1.isEmpty() && stack2.isEmpty();
        node1 = stack1.remove(stack1.size() - 1);
        node2 = stack2.remove(stack2.size() - 1);
        if (node1.val != node2.val)
            return false;
        node1 = node1.right;
        node2 = node2.right;
    }
}