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

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

说明:叶子节点是指没有子节点的节点。

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

     3
    / \
    9  20
    /  \
    15   7

返回它的最大深度3 。

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

题解

深度搜索

一个树的高度可以定义为max(lh,rh) + 1,即子树的最大深度加1。lh是左子树的高，rh是右子树的高。 对于本题来说只需要递归遍历整棵树就可以求解。

复杂度分析

时间复杂度是树的节点个数O(n)，空间复杂度依赖于树的深度，在树高度不超过栈深度的情况下可以使用， 最大复杂度为O(n),也就是树退化为链的情况。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return max(maxDepth(root.left),maxDepth(root.right))+1;
    }
private int max(int a,int b) {
    return a > b ? a: b;
}

}

广度搜索

二叉树的层次遍历其实也是一个广度搜索的过程，每一次都检索离父节点最近的节点. 深度搜索的过程中利用了栈来保存数据信息，广度搜索需要用其他的机制来记录当前访问的层次。 待添加题解。