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:
public class Solution { //Time: O(n) int min = Integer.MAX_VALUE; public int minDepth(TreeNode root) { if (root == null) { return 0; } getMin(root, 1); return min; } private void getMin(TreeNode root, int depth) { if (root.left == null && root.right == null) { min = Math.min(min, depth); } if (root.left != null) { getMin(root.left, depth + 1); } if (root.right != null) { getMin(root.right, depth + 1); } } }
BFS:
public class Solution { //Time: O(n) public int minDepth(TreeNode root) { if (root == null) { return 0; } int length = 1; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode cur = queue.poll(); if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } if (cur.left == null && cur.right == null) { return length; } } length++; } return length; } }
No comments:
Post a Comment