计算二叉树的高度

Question

我需要关于计算二叉树高度的理论的帮助，通常是符号。

我看过以下文章：

计算二叉树的高度

其中一个帖子给出了以下符号：

高度（节点）=最大值（高度（节点L）、高度（节点R））1

假设我有以下二叉树：

     10
   /   \  
  5    30
 / \   /  \ 
4  8  28  42

因此，我是否计算左节点（8）和右节点（42）的最大值，然后加上1？我不太明白这种符号是如何计算树的高度的。

Answer 1

你知道节点高度的定义吗？我的答案是到一片叶子的最远距离（所以所有叶子的高度都是0）...

Answer 2

树的高度是从根到树中最深节点的路径长度。下面是最短的算法

int height(Node root){
   if(root == null )
       return 0;
   return 1+max{height(root.left), height(root.right)};
}

Answer 3

我将尝试解释此递归算法的工作原理：

height(10) = max(height(5), height(30)) + 1

height(30) = max(height(28), height(42)) + 1
height(42) = 0 (no children)
height(28) = 0 (no children)

height(5) =  max(height(4), height(8)) + 1
height(4) = 0 (no children)
height(8) = 0 (no children)

因此，如果您想计算高度（10），您必须向下扩展递归，并向后替换结果。

height(5)  = max(0, 0) + 1
height(30) = max(0, 0) + 1
height(10) = max(1, 1) + 1
height(10) = 2

编辑：

如注释所示：
二叉树的高度=层数-1
因此应该假设空节点的高度等于-1，即：

height(empty) = -1 

或者

height(null) = -1 

这条路

height(42) = max(height(null), height(null)) + 1
height(42) = max(-1, -1) + 1
height(42) = -1 + 1
height(42) = 0

我已经更正了上面的计算。