javascript - 给定二叉搜索树和两个节点 n1 和 n2，编写一个函数来计算两个节点之间的距离

Question

给定一个二叉搜索树，我需要编写一个函数来查找 2 个节点之间的距离。我想我很喜欢这个，但它似乎不能正常工作。如果我想搜索树同一侧的节点之间的距离。不知道如何解决这个问题。任何提示将非常感谢。下面是我到目前为止的代码。我的代码使用 Javascript。

function Node(val){
  this.value = val;
  this.left = null;
  this.right = null;
}

function BinarySearchTree(value) { 
 this.root = null;
};

BinarySearchTree.prototype.push = function(val){
   var root = this.root;

   if(!root){
      this.root = new Node(val);
      return;
   }

   var currentNode = root;
   var newNode = new Node(val); 

   while(currentNode){
      if(val < currentNode.value){
          if(!currentNode.left){
             currentNode.left = newNode;
             break;
          }
          else{
             currentNode = currentNode.left;
        }
     }
     else{
         if(!currentNode.right){
            currentNode.right = newNode;
            break;
         }
         else{
            currentNode = currentNode.right;
         }
     }
  }

}

BinarySearchTree.prototype.levelOfNode = 
    function(root, key, level){
      if(root === null){
        return -1;
      }else if(root.value === key){
        return level;
      }
  let l = this.levelOfNode(root.left, key, level+1)
    if (l!== -1){
      return l;
    }
    return this.levelOfNode(root.right, key, level +1)
  }

BinarySearchTree.prototype.lca = function(root, n1, n2){
   if(!root) return;
   var val = root.value;
   if(n1<val && n2<val){
     return lca(root.left, n1, n2);
   }
   if(n1>val && n2>val){
     return lca(root.right, n1, n2);
  }
  return this.root;
}

BinarySearchTree.prototype.findDistance = function(root, n1, n2){
  let lcaValue = this.lca(root, n1, n2);

  let l1 = this.levelOfNode(lcaValue, n1, 0);
  let l2 = this.levelOfNode(lcaValue, n2, 0);

  return l1 + l2;

}

let tree = new BinarySearchTree();

tree.push(4);
tree.push(8);
tree.push(9);
tree.push(11);
tree.push(3);

tree.findDistance(4,8,11);

Answer 1

虽然你有一棵看起来像的树

   4
3     8
         9
           11

您可以从根目录获取每个目标的路径

[4, 8]
[4, 8, 9, 11]

消除所有公共(public)节点。然后检查一个路径数组是否为空，并取另一个路径数组的长度。

如果你有两个非空数组，你可以将两者的长度相加，比如

[4, 3]
[4, 8, 9]

去除公共(public)节点后

[3]
[8, 9]

然后将两个长度相加

1 + 2 = 3