算法练习26：二叉树的最大深度(leetcode 104)

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

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

深度优化算法

用前序遍历方法，遍历每个节点，当发现这个节点的左右节点都为空时，则为叶子节点，计算当前叶子节点高度，与历史最大高度对比，取最大高度。当遍历完所有节点后，就能得到最大深度。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0;
    let maxDept = 0;  // 最大深度  
    let curDept = 0;   // 当前叶子节点深度
    function preTravel(root) {
        if(!root) return;
        if(root) {
            // 前序遍历
            curDept++;  // 如果是非叶子节点，则深度+1
            preTravel(root.left)
            preTravel(root.right)
            if(curDept > maxDept) {
                maxDept = curDept;
            }
            curDept--;  // 当遍历完叶子节点时，回溯到上个节点，深度-1
        }
    }
    preTravel(root)
    return maxDept;  
};

• 时间复杂度：O(n)，因为每个节点都要被遍历一次
• 空间复杂度：O(height)，树的高度，因为要缓存从头节点到上个节点路径上的值