一、分治法
思路：
- 如果根节点为空，则返回0；
- 如果根节点的左子树和右子树都为空，则返回1；
- 如果左子树为空而右子树不为空，则返回右子树的深度+1；
- 如果右子树为空而左子树不为空，则返回左子树的深度+1；
- 如果左右子树都不为空，则返回Math.max(左子树，右子树)+1.
代码：
public int TreeDepth(TreeNode root){
if(root == null){
return 0;}
if(root.left==null || root.right==null){
return 1;
}
else if(root.left == null){
return TreeDepth(root.right)+1;
}
else if(root.right == null){
return TreeDepth(root.left)+1;
}
else{
return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
}
}
二、层次遍历
思路为：
- 首先创建一个队列（在java中可以用LinkedList实现），使用size表示队列中元素的个数；
- 定义一个count，初始化为0，表示弹出的次数
- 把根节点压入队列中，此时size = 1. 弹出根节点，count++，depth++
- 如果根节点的左右孩子不为空，那么把不为空的孩子压入队列中，再依次弹出，如果count == size，则代表这一层的所有元素全部弹完，depth++
- 递归
import java.util.LinkedList;
import java.util.Queue;
public int TreeDepth1(TreeNode root) {
if(root==null) {
return 0;
}
Queue<TreeNode> q=new LinkedList<TreeNode>();
q.add(root);
int d=0,count=0,nextcount=q.size();
while(q.size()!=0) {
TreeNode t=q.poll();
count++;
if(t.left!=null) {
q.add(t.left);
}
if(t.right!=null) {
q.add(t.right);
}
if(count==nextcount) {
d++;
count=0;
nextcount=q.size();
}
}
return d;
}
