在二叉搜索树中查找左右高度

Question

如何找到从根到树中最深节点的路径长度？我的意思是我可以使用 height() 方法找到树的 max height，如下代码所示。我可以通过该代码行找到最大高度 1 + Math.max(this._height(root.getleft()), this._height(root.getright()))。有任何方法可以找到 left 侧的高度和 right 侧的高度。谢谢，

const inputString1 = `13
    25
    39
    12
    19
    9
    23
    55
    31
    60
    35
    41
    70
    90`;
    //left 3 right 5
    const inputLines1: string[] = inputString1.split("\n");
    let leftHeight = 0;
    let rightHeight = 0;
    let currentLine1: number = 0;
    function readLine1(): string {
      return inputLines1[currentLine1++];
    }
    
    class TreeNode1<T> {
      private _value: T;
      public getvalue(): T {
        return this._value;
      }
      public setvalue(v: T) {
        this._value = v;
      }
    
      private _left: TreeNode1<T>;
    
      public getleft(): TreeNode1<T> {
        return this._left;
      }
    
      public setleft(node: TreeNode1<T>) {
        this._left = node;
      }
    
      private _right: TreeNode1<T>;
    
      public getright(): TreeNode1<T> {
        return this._right;
      }
    
      public setright(node: TreeNode1<T>) {
        this._right = node;
      }
    
      constructor(value: T) {
        this._value = value;
        this._left = null as any;
        this._right = null as any;
      }
    }
    
    class BinarySearchTree1<T> {
      leftHeight:number=0;
      rightHeight:number=0;
      height() {
        return this._height(this._root);
      }
    
      _height(root?: TreeNode1<T>): any {
        if (!root || (root.getleft() == null && root.getright() == null)) {
          return 0;
        }
    
        return (
          1 + Math.max(this._height(root.getleft()), this._height(root.getright()))
        );
      }
    
      private _root: TreeNode1<T>;
      public getroot(): TreeNode1<T> {
        return this._root;
      }
    
      public setroot(v: TreeNode1<T>) {
        this._root = v;
      }
      constructor() {
        this._root = null as any;
      }
    
      addToTree(v: T): boolean | undefined {
        const newNode = new TreeNode1(v);
        if (this._root == null) {
          this._root = newNode;
          return true;
        } else {
          let currentNode = this.getroot();
          let traversing = true;
          while (traversing) {
            if (currentNode != null) {
              if (currentNode.getvalue() == newNode.getvalue()) {
                traversing = false;
                return false;
              } else if (currentNode.getvalue() > newNode.getvalue()) {
                if (currentNode.getleft() == null) {
                  currentNode.setleft(newNode);
                  traversing = false;
                  return true;
                } else {
                  currentNode = currentNode.getleft();
                }
              } else {
                if (currentNode.getright() == null) {
                  currentNode.setright(newNode);
                  traversing = false;
                  return true;
                } else {
                  currentNode = currentNode.getright();
                }
              }
            }
          }
        }
      }
    
      BFS(): T[] {
        let queue = new Array<TreeNode1<T>>();
        let visited = new Array<T>();
        queue.push(this._root);
        while (queue.length != 0) {
          let currentNode = queue.shift();
          if (currentNode !== null) {
            visited.push(currentNode!!.getvalue());
          }
    
          if (currentNode !== null) {
            if (currentNode!!.getleft() !== null)
              queue.push(currentNode!!.getleft());
            if (currentNode!!.getright !== null)
              queue.push(currentNode!!.getright());
          }
        }
        return visited;
      }
    }
    
    function main1() {
      let myBST = new BinarySearchTree1<number>();
      for (let i = 1; i < inputLines1.length; i++) {
        myBST.addToTree(Number(inputLines1[i]));
      }
      console.log("BFS: " + myBST.BFS(), myBST.height());
      console.log(leftHeight, rightHeight);
    }
    
    main1();

Answer 1

首先，没有节点的树的高度是-1，可以在Wikipedia上阅读：

Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.

所以你的height方法应该更正为：

  _height(root?: TreeNode1<T>): number {
    if (!root) {
      return -1;
    }
    return (
      1 + Math.max(this._height(root.getleft()), this._height(root.getright()))
    );
  }

然后，删除 leftHeight 和 rightHeight 成员，并将它们设为 methods:

  leftHeight(): number {
    if (!this._root) {
      return -2;
    }
    return this._height(this._root.getleft());
  }
  rightHeight(): number {
    if (!this._root) {
      return -2;
    }
    return this._height(this._root.getright());
  }

...并在您的主函数中调用它们。

在二叉搜索树中查找左右高度

Finding left and right heigth in Binary Search Tree

typescript

binary-search-tree