java按顺序遍历两个二叉树，比较哪一个更大

Question

我试图找到一种方法来比较二叉树中的节点，看看一棵树的节点是否比另一棵树的节点“大”。我想要比较它们的方法是比较最左边的节点，根节点，然后是最右边的节点。我认为最好的方法是使用递归执行顺序遍历，并以这种方式比较节点

但是，在递归调用函数时，我很难找到返回正确答案的方法。递归确实有一种让我困惑的方法，它会让我忘记程序在做什么。我所拥有的是：

function binaryTreeComparison(node1, node2) {

        if node1 and node2 is null
            return 0
        
        if node1 is not null, but node2 is null
            return 1
        
        if node1 is null, but node2 is not null
            return -1
        
        else {
            binaryTreeComparison(node1.getLeftChild(), node2.getLeftChild())

            if node1 > node 2 
                return 1
            
            else if node1 = node 2
                return 0
            
            else if node1 < node2 
                return -1
            
            binaryTreeComparison(node1.getRightChild(), node2.getRightChild());
        }
        return 0
    }

为我尝试使用伪代码而道歉。试图创建一个最小的、可复制的示例。所发生的事情，不是中断并返回不同节点的第一个实例，而是返回“递归堆的顶部”，我不知道有什么方法可以绕过它。我确信这与我没有做像return binaryTreeComparison(node1.getLeftChild(), node2.getLeftChild());这样的事情有关。例如，如果我们有两个这样的二叉树：

     4           4
    / \         / \
   2   5       6   5

然后，它应该在访问左下角节点后返回-1，因为6>；2.取而代之的是，它返回0，因为它在树的顶部比较4=4。不同高度树木的另一个例子是：

     4           4
    / \         / \
   6   5       6   5
  /
 3

在这里，左树将大于右树，因此返回1。谢谢你的帮助。我找了很多其他地方寻求帮助，但我找不出答案

Answer 1

请注意，您的代码不是真正可复制的，因为它是伪代码，所以我不能100%确定您的问题是否正确，因为我不知道这个问题是否确实存在于您的代码中。在没有与问题无关的东西的情况下，用您正在使用的语言实际查看您的真实代码是非常有用的

然而，我已经实现了您在散文和伪代码中描述的内容，我相信我正在体验您的行为。我仍然不能100%肯定我完全理解您通过比较想要什么，但我希望这是有意义的：

基本上，你的结构是正确的。我认为你在左第一边的穿越上想得太多了。这似乎是人们在学习递归时经常遇到的问题。我在学习的时候经常遇到这个问题。相反，使用递归，您可以将范围缩小到最基本的情况，并让递归处理应用这些情况。在这种情况下，我认为您有大量的案例：

1. 节点1为空，节点2为空
2. 节点1为空，节点2不为空
3. 节点1不为空，节点2为空
4. 诺德的左撇子！=诺德的左撇子
5. 节点1的值！=节点2的值
6. node1是对的孩子！=node2的正确孩子
7. node1==node2

我不知道你的代码是什么样子的。在伪代码中，有两个主要问题。我假设第一个问题实际上不在代码中，即当您递归时，您没有检查并返回结果。您只想在以下情况下返回结果！=0.因此，不是：

binaryTreeComparison(node1.getLeftChild(), node2.getLeftChild())

你想要

leftResult = binaryTreeComparison(node1.getLeftChild(), node2.getLeftChild())
if (leftResult != 0) return leftResult

代码的关键问题是复制了条件（7）。这解释了您正在经历的行为：

instead of breaking off and returning the first instance of a node being different, it instead I think returns the "top of the recursion pile" and I don't know any way to get around this

实际上，您只想删除它，因为一旦您选中node1。价值<；点头2。值和节点2。价值>；点头2。值，您知道该节点1。value==node2。价值但是，您必须等到检查右侧后再返回0，否则您将始终忽略右侧的子项。相信底部的return 0可以工作：-）

下面是Python中的工作代码：

from dataclasses import dataclass

@dataclass
class Tree:
    value: int
    left: 'Tree' = None
    right: 'Tree' = None

def compare(node1: Tree, node2: Tree) -> int:
    if node1 is None and node2 is None:
        return 0
    if node1 is not None and node2 is None:
        return 1
    if node1 is None and node2 is not None:
        return -1

    left = compare(node1.left, node2.left)
    if left != 0:
        return left

    if node1.value > node2.value:
        return 1
    # This is your bug
    # if node1.value == node2.value:
    #     return 0
    if node1.value < node2.value:
        return -1

    right = compare(node1.right, node2.right)
    if right != 0:
        return right

    return 0