计算二叉树的高度

Question

我需要帮助计算二叉树高度的理论,通常是符号.

我看过以下文章:

计算二叉树的高度

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

height(node)= max(height(node.L),height(node.R))+ 1

我们假设我有以下二叉树:

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

因此,我是否计算左节点(8)和右边最大节点(42)的最大值,然后加1？我不太明白这种符号是如何工作的,以便计算树的高度.

Answer 1

我将尝试解释这种递归算法的工作原理:

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)

因此,如果要计算height(10),则必须向下扩展递归,而不是向后替换结果.

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

Answer 2

树的高度是树中从根到最深节点的路径长度.这是最短的算法

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