求二叉树的深度（递归和非递归）
Question
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
Answer
- 二叉树结构
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
- TreeDepth_1递归实现、TreeDepth_2非递归实现（Java描述）
package treedepth;
import java.util.LinkedList;
public class TreeDepth {
public int TreeDepth_1(TreeNode root) {
if(root == null) return 0;
int num1 = TreeDepth_1(root.left);
int num2 = TreeDepth_1(root.right);
return 1 + (num1 > num2 ? num1 : num2);
}
public int TreeDepth_2(TreeNode root) {
//level存放树的深度，LinkedList存放node结点
int level = 0;
LinkedList<TreeNode> q = new LinkedList<TreeNode>();
if(root == null) return 0;
q.offer(root); //放入根结点
int len = 0;
int cur; //记录本层已经记录的结点个数
while(!q.isEmpty()) {
len = q.size();
cur = 0;
while(cur < len) {
//出队
TreeNode current = q.poll();
cur++;
//如果当前左右子树还有结点，则将左右子树存放到链表中
if(current.left != null) {
q.offer(current.left);
}
if(current.right != null) {
q.offer(current.right);
}
}
//遍历存完一层的结点后level++
level++;
}
return level;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
