递归算法总结

我们解递归题的三部曲：

1. 找整个递归的终止条件：递归应该在什么时候结束？

2. 找返回值：应该给上一级返回什么信息？

3. 本级递归应该做什么：在这一级递归中，应该完成什么任务？

class Solution {    
public int maxDepth(TreeNode root) {        //终止条件：当树为空时结束递归，并返回当前深度0
        if(root == null){            
        return 0;
        }        //root的左、右子树的最大深度
        int leftDepth = maxDepth(root.left);        
        int rightDepth = maxDepth(root.right);        //返回的是左右子树的最大深度+1
        return Math.max(leftDepth, rightDepth) + 1;
    }
}