javascript - 在二叉搜索树上查找最小高度 - 如何跟踪高度的倒数第二个更新

Question

下面是我用来查找二叉搜索树 (BST) 的最小高度的代码。原始来源为here 。这里使用的最小高度的定义是从根节点到第一个不包含两个子节点的叶节点的距离。通过大量使用 console.logs，除了倒数第二个高度更新之外，我已经了解了所有内容。

如果运行下面的代码，倒数第五条日志表示:右为-1，左为-1，我理解。但是，它后面的日志指示更新“right”递归调用的值，将 right 的值设置为“right + 1”。 (因为右为 -1。-1 + 1 = 0)

因此，我期望以下结果:左 = -1，右 = 0。

最后递归调用后，再次将right设置为right + 1，我期望最终结果为Left:-1，right:1。

但是，输出是:左0，右:0。然后最终更新后，左:0，右:1。

那么，我错过了什么？左右变量如何同时更新？

/* Binary Search Tree */

class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

class BST {
  constructor() {
    this.root = null;
  }
  add(data) {
    const node = this.root;
    if (node === null) {
      this.root = new Node(data);
      return;
    } else {
      const searchTree = function(node) {
        if (data < node.data) {
          if (node.left === null) {
            node.left = new Node(data);
            return;
          } else if (node.left !== null) {
            return searchTree(node.left);
          }
        } else if (data > node.data) {
          if (node.right === null) {
            node.right = new Node(data);
            return;
          } else if (node.right !== null) {
            return searchTree(node.right);
          }
        } else {
          return null;
        }
      };
      return searchTree(node);
    }
  }
  findMinHeight(node = this.root) {
      if (node == null) {
          console.log("Minus 1")
          return -1;
      };
      console.log("Direction: L on node ", node.data);
      let left = this.findMinHeight(node.left);
      console.log("Direction: R on node ", node.data);
      let right = this.findMinHeight(node.right);
      console.log("RIGHT", right, "left", left)
      if (left < right) {
          console.log('Result = the value of LEFT + 1');
          return left + 1;
      } else {
          console.log('Result = the value of right + 1');
          return right + 1;
      };
  }
}



const bst = new BST();

bst.add(9);
bst.add(4);
bst.add(17);
bst.add(3);
// bst.add(6);
// bst.add(22);
// bst.add(5);
// bst.add(7);
// bst.add(20);

console.log(bst.findMinHeight());

Answer 1

要理解findMinHeight函数(下面我简化为f(node))，我认为有2个关键

1. 在本例中，递归函数从树的底部到顶部逐层返回值。
2. 我们可以发现f(currentNode)返回其分支的最小高度(我们可以将currentNode视为其分支的根)，以下是详细计算(以附图为例):

在 BST 的最底部，级别 (4,7,13)

case all: current node has no children at all.  
node.left=null => return -1
node.right=null => return -1
left!<right => return right+1=0 //(-1+1=0)
f(4)=f(7)=f(13)=0

进入下一级别，(1,6,14)

case 1: current node has no children at all.
node.left=f(null) => return -1
node.right=f(null) => return -1
left!<right => return right+1=0 //(-1+1=0)
f(1)=0

case 6: current node has two children.
node.left=f(4) => return 0
node.right=f(7) => return 0
left!<right => return right+1=1 //(0+1=1)
f(6)=1

case 14: current node has no children on the right.
node.left=f(13) => return 0
node.right=null => return -1
left!<right => return right+1=0 //(-1+1=0)
f(14)=0

进入下一个级别(3,10)，反之亦然，当向上传递值到下一个lvl时，下一个lvl节点返回其当前的minHeight，直到BST的顶部(8)，根级别如果把BST上每个节点返回的值写在它旁边，那就一目了然了。希望它可以帮助其他难以理解这一点的人。