题目
https://leetcode.com/problems/minimum-depth-of-binary-tree/
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 2
最短路径3-9,节点2个
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
思路
BFS比DFS合适
类似题:N叉树最大深度:https://www.cnblogs.com/inku/p/15642874.html
比如二叉树左边500右边1个节点
dfs先遍历完500个节点,再遍历1节点
bfs广度优先,左右俩边只要找到left和right同时为空的节点就返回
代码
DFS
public int minDepth(TreeNode root) {
if (root == null)
return 0; if (root.left == null && root.right == null)
return 1; if (root.left == null)
return minDepth(root.right) + 1;//left为空,走right if (root.right == null)
return minDepth(root.left) + 1;//right为空,走left return 1+Math.min(minDepth(root.left), minDepth(root.right));
//返回dfs后,左右中更小的,+1(root自身节点)
}
最大深度:https://www.cnblogs.com/inku/p/9854535.html
BFS
其实就是层次遍历
左右节点为空时就返回的限制,成了min
public int minDepth(TreeNode root) {
if(root==null)
return 0;
Queue<TreeNode> q=new LinkedList<>();
q.offer(root);
int ans=1;
while(!q.isEmpty()){
int size=q.size();
for(int i=0;i<size;i++) {
TreeNode cur=q.remove();
if (cur.left==null&&cur.right==null)
return ans;
if(cur.left!=null)
q.offer(cur.left);
if(cur.right!=null)
q.offer(cur.right);
}
ans++;
}
return ans;
}