作者:mobiledu2502861533 | 来源:互联网 | 2023-05-17 07:03
https:oj.leetcode.comproblemsminimum-depth-of-binary-treehttp:blog.csdn.netlinhuanmarsarti
https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
http://blog.csdn.net/linhuanmars/article/details/19660209
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int minDepth(TreeNode root)
{
if (root == null)
return 0;
// Solution A
// return minDepth_DFS(root, 1);
// Solution B
return minDepth_BFS(root);
}
//////////////////////////
// Solution A: DFS
//
private int minDepth_DFS(TreeNode node, int v)
{
if (node.left == null && node.right == null)
return v; // leaf
if (node.left == null)
{
return minDepth_DFS(node.right, v + 1);
}
else if (node.right == null)
{
return minDepth_DFS(node.left, v + 1);
}
else
{
return Math.min(minDepth_DFS(node.left, v + 1), minDepth_DFS(node.right, v + 1));
}
}
//////////////////////////
// Solution B: BFS
//
private int minDepth_BFS(TreeNode root)
{
Queue queue = new LinkedList<>();
root.val = 1;
queue.offer(root);
while (!queue.isEmpty())
{
TreeNode node = queue.poll();
if (node.left == null && node.right == null)
return node.val;
if (node.left != null)
{
node.left.val = node.val + 1;
queue.offer(node.left);
}
if (node.right != null)
{
node.right.val = node.val + 1;
queue.offer(node.right);
}
}
return -1; // Invalid case.
}
}
[LeetCode]111 Minimum Depth of Binary Tree