LeetCode 111. 二叉树的最小深度

题目链接：LeetCode 111. 二叉树的最小深度

题意：

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

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

解题思路：

1.递归法

与求最大深度类似，采用先序或者后序都是可以的，但是这里要注意一个问题：
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。是到叶子节点，
同时，不能直接照搬求最大深度的代码，

int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);
return result;

如果这么求的话，没有左孩子的分支会算为最短深度。(这样是不正确的)

所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。

反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

递归代码如下：

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left :=minDepth(root.Left)
    right := minDepth(root.Right)
    
    if  root.Left == nil && root.Right != nil { 
        return 1 + right;
    }
    if root.Left != nil  && root.Right == nil  { 
        return 1 + left;
    }
    return 1 + min(left,right)
}
func min(a,b int) int{
    if a < b{
        return a
    } 
    return b
}

2.迭代法：

对于迭代法，依然是层序遍历，
需要注意的是，只有当左右孩子都为空的时候，才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点

迭代代码如下：

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    var dep int
    var queue []*TreeNode
    queue = append(queue, root)
    for l := len(queue); l > 0; {
        dep++;
        for ; l > 0; l-- {
            node := queue[0]
            queue = queue[1:]
            if node.Left == nil && node.Right == nil {
                return dep
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            
        }
        l = len(queue)
    } 
    return dep
}