public class MinimumDepthOfBinaryTree {
static boolean isLeaf(TreeNode root){
if(root.left == null && root.right == null){
return true;
}
return false;
}
public static int run(TreeNode root) {
if(root != null){
TreeNode temRoot;
int count = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
root.val = 1;
while(queue.size() != 0){
temRoot = queue.poll();
int layer = temRoot.val;
if(isLeaf(temRoot)){
return layer;
}
if(temRoot.left != null){
queue.add(temRoot.left);
temRoot.left.val = temRoot.val + 1;
}
if(temRoot.right != null){
queue.add(temRoot.right);
temRoot.right.val = temRoot.val + 1;
}
}
}
return 0;
}
private static void build(TreeNode root) {
// TODO Auto-generated method stub
setLeft(root);
setRight(root);
setLeft(root.left);
setLeft(root.right);
}
public static void setLeft(TreeNode root){
root.left = new TreeNode(0);
}
public static void setRight(TreeNode root){
root.right = new TreeNode(0);
}
//运用层次遍历计算
public static void main(String[] args) {
TreeNode treeNode = new TreeNode(0);
build(treeNode);
System.out.println(run(treeNode));;
}
- 用层次遍历方法很简单,但是用深度遍历法则需要好好思考思考,递归就是整体考虑,就把run当做了求最小值的方法
class Solution {
public:
int run(TreeNode *root)
{
if(root == nullptr) return 0;
if(root->left == nullptr) // 若左子树为空,则返回右子树的最小深度+1
{
return run(root->right)+1;
}
if(root->right == nullptr) // 若右子树为空,则返回左子树的最小深度+1
{
return run(root->left)+1;
}
// 左右子树都不为空时,取较小值
int leftDepth = run(root->left);
int rightDepth = run(root->right);
return (leftDepth<rightDepth)?(leftDepth+1):(rightDepth+1);
}
};
网友评论