求讲解 二叉树求高度的递归算法

Question

这是一个二叉树求高度的算法 我看了半天没弄明白 他是递归比较两个左子树和右子树的高度 然后再把较大的那个+1 得到二叉树的高度 但是他的递归是到底怎样算出高度的？？？就是最后那句 怎么算出高度的？？？？
public int height(BinaryTreeNode p) {  //p是一个二叉树根节点的引用
    if(p == null){
       System.out.println("高度为0")
       return 0;
     }else{
       return 1 + max(height(llink),height(rlink));  //这个LLINK 和RLINK分别是p的两个指针，指向左子树和右子树
     }
}

Answer 1

你可以这样理解：
首先你就当height可以求出某个节点的高度
从根节点开始，怎么表示这棵树的高度？根节点一层，左右子树，谁层数多，当然加上谁的啦
所以 return 1 + max(height(llink),height(rlink))；
然后对llink或者rlink都是同样的理解
最后什么时候返回？当然是节点为空的时候啦，因为一个叶子节点已经是最后一层，它的左右节点
都是空的。希望能帮到lz

Answer 2

左子树的高度height(llink)
右子树的高度height(rlink)
这两个高度当然要取更大的数 对吧
加上自己的节点 1：
       本次递归的p------> O(p)
                       /  \
                      /    \
height(llink)------>左子树  右子树<----------height(rlink)
总的高度 为 1 + max(height(llink),height(rlink));  

Answer 3

排版有点问题左子树的高度height(llink) 
右子树的高度height(rlink) 
这两个高度当然要取更大的数 对吧 
加上自己的节点 1： 
      本次递归的p------> O(p) 
                      /  \ 
                     /    \ 
height(llink)------>左子树  右子树 <----------height(rlink) 
总的高度 为 1 + max(height(llink),height(rlink)); 
 

Answer 4

先看一个求和的简单例子吧
public class test
{ public static void main(String[] args)
{
System.out.println(sum(1, 2)); } public static int sum(int a, int b)
{
if (a == b)
{
return a;
}
return a + sum(a + 1, b);
}}