algorithm - 获取二叉树中给定值的根到节点的距离 : Algorithm correctness

Question

这是我的代码

 public int getDist(Node root, int value)
  {
    if (root == null && value !=0)
      return -1;//
    if(root.value == value)// we have a match
      return 0;
    if(root.getLeft()!=null)
    int left =1+ getDist(root.getLeft(),value);
    int right = 1+getDist(root.getRight(),value);
    if(left ==-1 &&  right== -1)
      return -1;//not found
    return Math.max(left,right);
  }

对于上述方法的正确性或任何优化的任何反馈，我将不胜感激。

Answer 1

就目前而言，您的代码不会按预期工作。另一方面考虑一下:

public int getDist(Node root, int value) {

    // value is never in an empty subtree
    if (root == null)
        return -1;

    // found value, distance from root is 0
    if(root.value == value)
        return 0;

    // find distance from root of left subtree
    int left = getDist(root.getLeft(),value); 

    // find distance from root of right subtree
    int right = getDist(root.getRight(),value);

    // value not found in either subtree
    if(left == -1 && right == -1) 
        return -1;

    // if the value was found,
    // return the distance from the root of the subtree + 1
    return 1 + Math.max(left,right); 
}

我所做的更改是删除一些多余的检查并在检查“值不在任一子树中”之后移动 +1。其效果如下:如果递归发现该值不在子树中，则 return 语句会将值 -1 一直波纹到子树的根而不改变它，保持信息“值不在这里”不变。如果在至少一个子树中找到该值，则 left 和 right 不可能都是 -1，因此检查将失败，最后的 return 语句将返回预期值。