描述
给定一个二叉树，找出其最小深度。
二叉树的最小深度为根节点到最近叶子节点的距离
样例
给出一棵如下的二叉树:
1
/ \
2 3
/ \
4 5
这个二叉树的最小深度为 2
代码
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
- 分治+递归
public class Solution {
/*
* @param root: The root of binary tree
* @return: An integer
*/
public int minDepth(TreeNode root) {
int mindepth = helper(root);
return mindepth;
}
private int helper(TreeNode root) {
if (root == null) {
return 0;
}
int leftMinDepth = helper(root.left);
int rightMinDepth = helper(root.right);
// 不要忘记考虑左右子树可能存在空子树的情形
// 除了空子树深度为 0，即使只有一个结点，深度还等于 1
if (leftMinDepth == 0 || rightMinDepth == 0) {
return Math.max(leftMinDepth, rightMinDepth) + 1;
}
int min_depth = Math.min(leftMinDepth, rightMinDepth) + 1;
return min_depth;
}
}
- 遍历+递归
public class Solution {
/*
* @param root: The root of binary tree
* @return: An integer
*/
private int depth = Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
traversal(root, 1);
return depth;
}
private void traversal(TreeNode node, int curDepth) {
// 要注意写递归出口，遍历中结点的左右儿子可能为空
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
if (curDepth < depth) {
depth = curDepth;
}
}
traversal(node.left, curDepth + 1);
traversal(node.right, curDepth + 1);
}
}
