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.
DFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| * Definition for a binary tree node. * 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; if (root.left == null) return minDepth(root.right) + 1; if (root.right == null) return minDepth(root.left) + 1; return Math.min(minDepth(root.left),minDepth(root.right)) + 1; } }
|
BFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| * Definition for a binary tree node. * 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) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 0; while (queue.peek() != null) { i++; int k = queue.size(); for (int j = 0; j < k; j++) { TreeNode cur = queue.peek(); if (cur.left != null) queue.offer(cur.left); if (cur.right != null) queue.offer(cur.right); queue.poll(); if (cur.left == null && cur.right == null) return i; } } } return 0; } }
|