java - 树中相邻 child 的比较不会发生？

Question

这个方法有什么问题？似乎但我不确定树中相邻 child 的比较不会发生。

我粗略地手工追踪了这个算法的工作原理，我认为这个想法是正确的，也许实现有问题，或者我不知道递归是如何工作的，第二个辅助(比较)方法似乎是问题所在

public static int MAX(BST B) {
  int m = ((Integer) B.root.data).intValue();
  return call(B.root, m);
}

public static int call(node current, int max) {   
  //first helper method gets the max from two different levels in the tree
  if(current == null)
    return -1;
  if(current.left == null && current.right == null)
    return max;
  else {
    if(((Integer) current.data).intValue()>max)
      max = ((Integer) current.data).intValue();
    return compare(call(current.left,max),call(current.right,max));
  }
}

//second helper method gets the max
static int compare(int m1, int m2) {
  if(m1>m2)
    return m1;
  else 
    return m2;
}

Answer 1

由于您正在搜索整棵树，我将假设该结构没有正确排序。

错误在你的调用函数中:

 if(current.left==null&&current.right==null) return max;

假设您有一棵树，其根有两个叶节点(总共三个节点)。根的值为 3，右边的值为 2，左边的值为 5。算法应返回 5，但您的代码将返回 3。这是因为您忽略了任何叶子(没有“子节点”的节点)的值那行代码。因此，在此示例中，您的代码忽略值 5，并返回 max，即 3。

当 left 和 right 为 null 时，您可以通过返回 compare(current.value, max) 来解决这个问题。