104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3<br />   / \<br />  9  20<br />    /  \<br />   15   7<br />返回它的最大深度 3 。

/**
 * 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 {

    function maxDepth($root){
        if($root == null) return 0;
        $maxDepth = 1;
        if($root->left == null && $root->right == null){
            return 1;
        }
        $leftMaxDepth = $this->maxDepth($root->left);
        $rightMaxDepth = $this->maxDepth($root->right);
        return ($leftMaxDepth > $rightMaxDepth) ? $leftMaxDepth + $maxDepth : $rightMaxDepth + $maxDepth;
    }

//时间复杂度：O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
//空间复杂度：O(height)，其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function maxDepth($root) {
        if($root == null){
            return 0;
        }

        $queue = new SplQueue();
        $queue->enqueue($root);
        $ans = 0;
        while(!$queue->isEmpty()){

            (int) $size = $queue->count();
            while($size > 0){
                $node = $queue->dequeue();
                if($node->left != null)
                    $queue->enqueue($node->left);

                if($node->right != null)
                    $queue->enqueue($node->right);

                $size--;
            }
            $ans++;
        }

        return $ans;
    }
}

```

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。