L1-二叉树的最小深度

Posted on |

题目描述

给定一个二叉树，找出其最小深度。

二叉树的最小深度为根节点到最近叶子节点的距离。
样例
给出一棵如下的二叉树:

    1
 /     \ 
2       3
      /    \
     4      5

这个二叉树的最小深度为 2

解题思路

1.空树 最小深度为0

2.左子树为空，右子树不为空 –> 右子树的的叶子节点 （可以把左子树的节点Max_value）
或者 右子树为空，左子树不为空 —->左子树的的叶子节点

3.左右子树都不为空 —>左右子树最近的叶子节点 （想到用min）

4.左右子树都空 最小深度为1

代码

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
31
/**
 * 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) {
        // write your code here
        int a,b;
        if(root==null) return 0;
        if(root.left==null&&root.right==null) return 1;
        if(root.left!=null)
        a=minDepth(root.left);
       else a=Integer.MAX_VALUE;
       if(root.right!=null)
       b=minDepth(root.right);
  else b=Integer.MAX_VALUE;
return Math.min(a,b)+1;
    }
}

注意:与L1-二叉树的最大深度的区别