英文:
Equivalent sorted binary tree In Java
问题
我正在学习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)); // 输出 true
我想知道是否有其他更好的方法来用Java解决这个问题？
英文:
I am learning Go and in this tutorial, concurrency and channels can be used to complete this exercise: Solution.
And I try to solve this by Java. The solution I can think of is to use temporary data structure to store the results of the in-order traversal of these two trees, and then compare.
For example, I use a StringBuilder to store the result of the in-order traversal and then compare(Notice that we're comparing sorted binary trees):
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);
}
Testcase:
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
I want to know is there any other better way to solve this by Java?
答案1
得分: 0
你可以同时遍历这两棵树，并立即比较它们的元素，而无需使用 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;
}
}
希望对你有帮助！
英文:
You can walk both trees at the same time and compare their elements immediately without using a StringBuilder.
Something along the lines:
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;
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论