递归填充二叉搜索树的高度

Question

我有一个家庭作业问题，要求编写一个递归填充二叉搜索树高度的方法。

下面是我的代码

我

检查了这个问题的答案键，这是有道理的，但我想知道我的方法是否是另一种有效的方法。

public static <T extends Comparable> void fillsHeight(BSTNode root){
        if (root == null) return;
        if (root.left == null && root.right == null) root.height = 0;
        if (root.left != null) height = root.left.height + 1;
        if (root.right != null) height = Math.max(height, root.right.height) + 1;

        fillsHeight(root.left);
        fillsHeight(root.right);
    }

以下是答案键的官方解决方案：

 public static <T extends Comparable> 
   void fillHeights(BSTNode root) {
      if (root == null) { return; }
      fillHeights(root.left);
      fillHeights(root.right);
      root.height = -1;
      if (root.left != null) {
         root.height = root.left.height;
      }
      if (root.right != null) {
         root.height = Math.max(root.height, root.right.height);
      }
      root.height++;  
   }

Answer 1

该解决方案的重要性在于，它首先使用 fillHeights(root.left); 和 fillHeights(root.right); 递归调用根左右子树，然后才比较结果。

您还错过了实际增加节点高度的重要部分，root.height++;