题目:
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.
Tree Depth-first Search链接: http://leetcode.com/problems/minimum-depth-of-binary-tree/
题解:
求二叉树最短路径长度。依然使用DFS递归求解。
Time Complexity - O(n), Space Complexity - O(n)。
public class Solution { public int minDepth(TreeNode root) { if(root == null) return 0; if(root.left != null && root.right != null) return 1 + Math.min(minDepth(root.left), minDepth(root.right)); else if(root.left == null) return 1 + minDepth(root.right); else return 1 + minDepth(root.left); } }
Update:
/** * 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 1 + minDepth(root.right); else if(root.right == null) return 1 + minDepth(root.left); else return 1 + Math.min(minDepth(root.left), minDepth(root.right)); } }
二刷:
要注意题目规定最短路径必须是非空leaf node,所以我们要对root.left 或者root.right为空时进行判断。 这道题目也可以用BFS层序遍历来做,这样的话可以避免很多不必要的查找。
Java:
Recursive:
Time Complexity - O(n), Space Complexity - O(n)。
/** * 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 1 + minDepth(root.right); } else if (root.right == null) { return 1 + minDepth(root.left); } else { return 1 + Math.min(minDepth(root.left), minDepth(root.right)); } } }
三刷:
Java:
DFS:
/** * 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 1 + minDepth(root.right); } else if (root.right == null) { return 1 + minDepth(root.left); } else { return 1 + Math.min(minDepth(root.left), minDepth(root.right)); } } }
BFS:
/** * 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; } Queue<TreeNode> q = new LinkedList<>(); q.offer(root); int curLevel = 1, nextLevel = 0; int depth = 1; while (!q.isEmpty()) { TreeNode node = q.poll(); curLevel--; if (node.left == null && node.right == null) { return depth; } if (node.left != null) { q.offer(node.left); nextLevel++; } if (node.right != null) { q.offer(node.right); nextLevel++; } if (curLevel == 0) { curLevel = nextLevel; nextLevel = 0; depth++; } } return depth; } }
Reference:
https://leetcode.com/discuss/25060/my-4-line-java-solution
https://leetcode.com/discuss/61476/bfs-c-8ms-beats-99-94%25-submissions