104. 二叉树的最大深度

题意：

解题思路：

思路：
递归(dfs)：O(n)：树中的每个节点遍历一次
1. 递归求左右子树高度最大值，直到子树为空，最后返回该最大值；

PHP代码实现：

class Solution {
    /**
     * @param TreeNode $root
     * @return Integer
     */
    function maxDepth($root) {
        if ($root == null) return 0;
        return max($this->maxDepth($root->left), $this->maxDepth($root->right)) + 1;
        //return $this->maxDepthIterative($root);
        if (!$root) return 0;
        return max($this->getHeight($root->left), $this->getHeight($root->right)) + 1;
    }
    function getHeight($root) {
        if ($root == null) return 0;
        $left = $this->getHeight($root->left);
        $right = $this->getHeight($root->right);
        return max($left, $right) + 1;
    }
    function maxDepthIterative($root) {
        if ($root == null) return 0;
        $queue = [];
        array_push($queue, $root);
        $depth = 0;
        while (!empty($queue)) {
            foreach ($queue as $r) {
                if ($r->left != null) array_push($queue, $r->left);
                if ($r->right != null) array_push($queue, $r->right);
                array_shift($queue);
            }
            ++$depth;
        }
        return $depth;
    }
}

GO代码实现：

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    var result int
    queue := make([]*TreeNode,0)
    queue = append(queue,root)
    for len(queue) != 0 {
        levelLength := len(queue)
        for levelLength > 0 {
            levelLength--;
            node := queue[0] // 出队
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue,node.Left)
            }
            if node.Right !=  nil {
                queue = append(queue,node.Right)
            }
        }
        result++;
    }
    return result
}