java 求二叉树的深度 / 节点总数
1.判断根节点是否为空
2.递归获取左子树的深度
3.递归获取右子树的深度
- public int hight(Node node){
- if(node==null){
- return 0;
- }else{
- int i=hight(node.getLeftChild());
- int j=hight(node.getRightChild());
- return (i<j)?(j+1):(i+1);
- }
- }
讲一下这里的递归原理:当遍历到C和E时,左子树node.getLeftChild()和右子树node.getRightChild()返回0+1,此时深度为1,当到B和D时,B和D的深度都为1,此时返回1+1=2,同理,一步一步往回退,直到左右子树遍历一遍得到左右子树的深度然后进行比较返回最大的值+1就是整棵树的深度。
那么求二叉树的所有节点的个数,递归原理与此相同。
求二叉树节点总数:
求二叉树的节点数:返回左子树和右子树个数的和,然后加上一个根节点
- public int sumNode(Node node){
- if(node==null){
- return 0;
- }else{
- int a=sumNode(node.getLeftChild());
- int b=sumNode(node.getRightChild());
- return 1+a+b;
- }
- }