中序遍历两棵二叉树比较哪个大

Question

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

但是，在递归调用函数时，我无法找到 return 正确答案的方法。递归确实有一种让我困惑的方式，让我无法理解程序在做什么。我有以下内容：

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
    }

对我尝试使用伪代码表示歉意。试图创建一个最小的、可重现的例子。发生了什么，而不是中断和 returning 节点的第一个实例是不同的，相反我认为 returns 是“递归堆的顶部”而且我不知道有什么办法解决这个问题。我确定这与我没有做 return binaryTreeComparison(node1.getLeftChild(), node2.getLeftChild()); 之类的事情有关。例如，如果我们有两个像这样的二叉树：

     4           4
    / \         / \
   2   5       6   5

然后它应该在访问左下角节点后 return -1，因为 6 > 2。相反发生的是它 returns 0 因为它在顶部比较 4 = 4树的。不同高度的树的另一个例子是：

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

这里左边的树会比右边的树大，因此 returning 1。谢谢你的帮助。我搜索了很多其他地方寻求帮助，但我无法弄清楚。

Answer 1

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

但是，我已经实现了您在散文和伪代码中描述的内容，并且我相信我正在经历您的行为。我仍然不是 100% 确定我完全理解你想要的东西，但我希望这是有道理的：

基本上，你的结构是正确的。我认为你过度考虑了从左第一侧向下的遍历。这似乎是人们在学习递归时经常遇到的问题。我在学习的时候经常犯这个问题。相反，通过递归，您可以将事情缩小到最基本的情况，并让递归处理应用它们。在这种情况下，我认为您有很多情况：

节点 1 为空，节点 2 为空
节点 1 为空且节点 2 不为空
节点 1 不为空且节点 2 为空
node1 左侧 child != node2 左侧 child
node1 的值 != node2 的值
node1 的右边 child != node2 的右边 child
节点 1 == 节点 2

我不太清楚你的代码是什么样的。在您的 pseudo-code 中，有两个主要问题。我假设第一个问题实际上不在您的代码中，即当您递归时，您没有检查和 returning 结果。您只想 return 如果结果 != 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.value < node2.value 和 node2.value > node2.value，你知道即 node1.value == node2.value。但是，你必须等到after你在returning 0之前检查右边，否则你将永远忽略右边的children。相信底部的 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

中序遍历两棵二叉树比较哪个大

In-order traversal of two binary trees to compare which one is bigger

java

recursion

binary-tree

nodes

inorder