本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
建议优先阅读，该文详细介绍了二叉树不同遍历方式的各种实现。
111. 二叉树的最小深度
本题来自 LeetCode：二叉树的最小深度[1]
题目详情
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树
[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回它的最小深度
2.
广度优先搜索（层次遍历）
广度优先搜索，其实是采用层次遍历法，主要逻辑是找到
第一个出现的叶子节点的层数。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null) {
return 0;
}
ListTreeNode queue = new LinkedList();
// 根节点入队
queue.add(root);
int depth = 0;
while(!queue.isEmpty()) {
// 记录当前层的节点个数
int size = queue.size();
// 深度自增
depth ++;
// 依次处理当前层（前size个）节点
for(int i = 0; i size; i ++) {
TreeNode node = queue.remove(0);
// 找到第一个叶子节点
if(node.left == null && node.right == null) {
return depth;
}
// 左子树入队
if(node.left != null) {
queue.add(node.left);
}
// 右子树入队
if(node.right != null) {
queue.add(node.right);
}
}
}
return depth;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(n)
深度优先搜索
深度优先搜索，需要
比较每个叶子节点的深度，获取最小深度；
class Solution {
// 记录最小深度
int minDepth = Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
if(root == null) {
return 0;
}
dfs(root, 0);
return minDepth;
}
public void minDepth(TreeNode root, int currentDepth) {
// 层数自增
currentDepth ++;
// 若当前节点是叶子节点，比较深度
if(root.left == null && root.right == null) {
minDepth = Math.min(minDepth, currentDepth);
return;
}
// 深度优先，处理左子树
if(root.left != null) {
dfs(root.left, currentDepth);
}
// 深度优先，处理右子树
if(root.right != null) {
dfs(root.right, currentDepth);
}
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(n)，递归调用栈
104. 二叉树的最大深度
本题来自 LeetCode：104. 二叉树的最大深度[2]
题目详情
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉
[3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
广度优先搜索（层次遍历）
广度优先搜索，其实是采用层次遍历法，主要逻辑是
计算二叉树的深度，完成一次完整的层次遍历就可以得到其深度。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
ListTreeNode queue = new LinkedList();
// 根节点入队
queue.add(root);
int depth = 0;
while(!queue.isEmpty()) {
// 记录当前层的节点个数
int size = queue.size();
// 深度自增
depth ++;
// 依次处理当前层（前size个）节点
for(int i = 0; i size; i ++) {
TreeNode node = queue.remove(0);
// 左子树入队
if(node.left != null) {
queue.add(node.left);
}
// 右子树入队
if(node.right != null) {
queue.add(node.right);
}
}
}
return depth;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(n)
深度优先搜索
深度优先搜索，和最小深度类似，需要
比较每个叶子节点的深度，获取最大深度；
class Solution {
// 记录最大深度
int maxDepth = 0;
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
dfs(root, 0);
return maxDepth;
}
public void dfs(TreeNode root, int currentDepth) {
// 层数自增
currentDepth ++;
// 若当前节点是叶子节点，比较深度
if(root.left == null && root.right == null) {
maxDepth = Math.max(maxDepth, currentDepth);
return;
}
// 深度优先，处理左子树
if(root.left != null) {
dfs(root.left, currentDepth);
}
// 深度优先，处理右子树
if(root.right != null) {
dfs(root.right, currentDepth);
}
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(n)，递归调用栈
993. 二叉树的堂兄弟节点
本题来自 LeetCode：993. 二叉树的堂兄弟节点[3]
题目详情
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度
k+1处。
如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点
root，以及树中两个不同节点的值
x和
y。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。
示例 1：
1
/
2 3
/
4
输入：root = [1,2,3,4], x = 4, y = 3
输出：false
示例 2：
1
/
2 3
4 5
输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true
示例 3：
1
/
2 3
4
输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false
提示：
二叉树的节点数介于 2 到 100 之间。
每个节点的值都是唯一的、范围为
1到
100的整数。
广度优先搜索（层次遍历）
广度优先搜索，其实是采用层次遍历法，由于每个节点的值都是唯一的，只需判断是否能在同一层找到这个两个数，
并且他们的父节点不是同一个。
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
if(root == null) {
return false;
}
ListTreeNode queue = new LinkedList();
// 根节点入队
queue.add(root);
// 找到了其中一个节点
boolean foundOne = false;
while(!queue.isEmpty()) {
// 记录当前层的节点个数
int size = queue.size();
// 依次处理当前层（前size个）节点
for(int i = 0; i size; i ++) {
TreeNode node = queue.remove(0);
// 判断该节点的左右子节点是否为所给的两个节点
if(node.left != null && node.right != null) {
// 若是，则表示所给的两个节点不是堂兄弟节点
if((node.left.val == x || node.left.val == y)
&& (node.right.val == x || node.right.val == y)) {
return false;
}
}
// 匹配两个节点是否在本层
if(node.val == x || node.val == y) {
// 该层找到了两个节点
if(foundOne) {
return true;
} else {
// 找到其中一个
foundOne = true;
}
}
// 左子树入队
if(node.left != null) {
queue.add(node.left);
}
// 右子树入队
if(node.right != null) {
queue.add(node.right);
}
}
// 表示在该层只找到了其中一个节点
if(foundOne) {
return false;
}
}
return false;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(n)
参考资料
二叉树的最小深度: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
二叉树的最大深度: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
二叉树的堂兄弟节点: https://leetcode-cn.com/problems/cousins-in-binary-tree/
原文始发于微信公众号（xiaogan的技术博客）：
