1，递归
这题最容易想到的就是递归，啥叫“递归”，也就是下面这张图
开个玩笑，我们画个图来看下
原理很简单，代码如下
public int TreeDepth(TreeNode root) {
return root==null? 0 : Math.max(TreeDepth(root.left), TreeDepth(root.right))+1;
}看一下运行结果
2，BFS
BFS的实现原理就是一层层遍历，统计一下总共有多少层，我们来画个图分析一下。
代码如下
public int TreeDepth(TreeNode root) {
if (root == null)
return 0;
//创建一个队列
Deque<TreeNode> deque = new LinkedList<>();
deque.push(root);
int count = 0;
while (!deque.isEmpty()) {
//每一层的个数
int size = deque.size();
while (size-- > 0) {
TreeNode cur = deque.pop();
if (cur.left != null)
deque.addLast(cur.left);
if (cur.right != null)
deque.addLast(cur.right);
}
count++;
}
return count;
}我们再来看一下运行时间，显然效率不是很高
3，DFS
我们可以使用两个栈，一个记录节点的stack栈，一个记录节点所在层数的level栈，stack中每个节点在level中都会有一个对应的值，并且他们是同时出栈，同时入栈
public int TreeDepth(TreeNode root) {
if (root == null)
return 0;
//stack记录的是节点，而level中的元素和stack中的元素
//是同时入栈同时出栈，并且level记录的是节点在第几层
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> level = new Stack<>();
stack.push(root);
level.push(1);
int max = 0;
while (!stack.isEmpty()) {
//stack中的元素和level中的元素同时出栈
TreeNode node = stack.pop();
int temp = level.pop();
max = Math.max(temp, max);
if (node.left != null) {
//同时入栈
stack.push(node.left);
level.push(temp + 1);
}
if (node.right != null) {
//同时入栈
stack.push(node.right);
level.push(temp + 1);
}
}
return max;
}运行结果
参考：
367，二叉树的最大深度
403，验证二叉搜索树
401，删除二叉搜索树中的节点
400，二叉树的锯齿形层次遍历
399，从前序与中序遍历序列构造二叉树
388，先序遍历构造二叉树
387，二叉树中的最大路径和
375，在每个树行中找最大值
374，二叉树的最小深度
373，数据结构-6,树
372，二叉树的最近公共祖先
我把部分算法题整理成了PDF文档，截止目前总共有900多页，大家可以下载阅读
链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
京公网安备 11010502036488号