描述：求给定二叉树的最大深度
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。
一、广度优先思路实现（bfs）
通过队列实现
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
* 一层一层遍历二叉树 并存入到队列中，然后每遍历一层让count++；
* @param root TreeNode类
* @return int整型
*/
public int maxDepth (TreeNode root) {
// write code here
if(root==null){
return 0;
}
ArrayDeque<TreeNode> deque=new ArrayDeque<TreeNode>();
int count=0;
deque.add(root);
while(!deque.isEmpty()){
count++;
int n=deque.size();
for(int i=0;i<n;i++){ //遍历当前层，把下一层加入到队列中
TreeNode treeNode=deque.poll();
if(treeNode.left!=null){
deque.add(treeNode.left);
}
if(treeNode.right!=null){
deque.add(treeNode.right);
}
}
}
return count;
}
}
二、深度优先思路实现（dfs）
通过两个栈实现，同时出栈，同时入栈。
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
* 搭配两个栈实现，一个栈存节点、一个栈存当前节点的所在层数
*
* @param root TreeNode类
* @return int整型
*/
public int maxDepth (TreeNode root) {
// write code here
if(root==null)
return 0;
Stack<TreeNode> stackNode=new Stack<TreeNode>();
Stack<Integer> stackCount=new Stack<Integer>();
stackNode.push(root);
stackCount.push(1);
int max=0;
while(!stackNode.isEmpty()){
int temp=stackCount.pop();
TreeNode tree=stackNode.pop(); //一直取最后存入的，即先完成一个分支的深度遍历
if(temp>max){
max=temp; //保证max存入的一直是最大的层数深度
}
if(tree.left!=null){
stackNode.push(tree.left);
stackCount.push(temp+1);
}
if(tree.right!=null){
stackNode.push(tree.right);
stackCount.push(temp+1);
}
}
return max;
}
}