111. 二叉树的最小深度

题意：

解题思路：

思路：每个节点仅被遍历一次，且遍历时所有操作的复杂度是 O(1)，所以总时间复杂度是 O(n)
1. 如果root左右节点都为空，则返回1
2. 如果root左节点为空，则递归求右子树节点的深度+1
3. 如果root右节点为空，则递归求左子树的深度+1
4. 当 root节点左右孩子都不为空时，返回左右子树较小深度的节点值+1（加上根节点这层）

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Integer
     */
    function minDepth($root) {
        return $this->minDepthIterative($root);
        if (!$root) return 0;
        if ($root->left == null && $root->right == null) return 1;
        if ($root->left == null) return $this->minDepth($root->right) + 1;
        if ($root->right == null) return $this->minDepth($root->left) + 1;
        return min($this->minDepth($root->left), $this->minDepth($root->right)) + 1;
    }
    function minDepthIterative($root) {
        if (!$root) return 0;
        $queue = [];
        array_push($queue, $root);
        $depth = 1;
        while (!empty($queue)) {
            foreach ($queue as $r) {
                if ($r->left == null && $r->right == null) return $depth;
                if ($r->left != null) array_push($queue, $r->left);
                if ($r->right != null) array_push($queue, $r->right);
                array_shift($queue);
            }
            ++$depth;
        }
        return -1;
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    if root == nil { return 0 }
    if root.Left == nil && root.Right == nil {
        return 1
    }
    if root.Left != nil && root.Right == nil {
        return minDepth(root.Left) + 1
    }
    if root.Right != nil && root.Left == nil {
        return minDepth(root.Right) + 1
    }
    return min(minDepth(root.Left), minDepth(root.Right)) + 1
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    depth := 0
    if root == nil {
        return depth
    }
    var queue []*TreeNode
    queue = append(queue, root)
    for len(queue) > 0 {
        qLen := len(queue)
        depth++
        for i := 0; i < qLen; i++ {
            if queue[i].Right == nil && queue[i].Left == nil {
                return depth
            }
            if queue[i].Left != nil {
                queue = append(queue, queue[i].Left)
            }
            if queue[i].Right != nil {
                queue = append(queue, queue[i].Right)
            }
        }
        queue = queue[qLen:]
    }
    return depth
}