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

求讲解 二叉树求高度的递归算法
这是一个二叉树求高度的算法 我看了半天没弄明白 他是递归比较两个左子树和右子树的高度 然后再把较大的那个+1 得到二叉树的高度 但是他的递归是到底怎样算出高度的？？？就是最后那句 怎么算出高度的？？？？

Java code

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的两个指针，指向左子树和右子树     }}

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

希望能帮到lz
[解决办法]
排版有点问题

Java code

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

 

查看更多 下一篇