1.理解题目

所谓二叉树的最大深度，其实就是二叉树的高度。我们要找到从根节点到最远的叶子节点的长度。

2.解题思路

这个题有两种解题思路，一种就是自顶向下，计算每条路径的长度，然后更新最大值，也就是回溯（dfs）；另外一种方法就是自底向上，使用后序遍历，往上依次返回当前节点最大深度，其实就是递归的思路，其递推关系就是：Max(左孩子结点的高度, 右孩子结点的高度)+1

2.1.回溯（dfs）

回溯就是将每个到叶子节点的路径的长度全部计算出来，然后更新找到最大值。实际上，我在写的时候发现，深度优先遍历二叉树，其实就是二叉树的先序遍历。这就和下面递归的后序遍历对应上了

这里我们的count指代的走过的节点路径的长度，所以刚开始的赋值为0，这主要是为了，让我们写base case的时候更加方便。

int max = 0;
public int maxDepth(TreeNode root) {
    backtracking(root, 0);
    return max;
}
public void backtracking(TreeNode root, int count){
    if(root == null){
        max = Math.max(max, count);
        return;
    }
    backtracking(root.left, count+1);
    backtracking(root.right, count+1);
}

2.2.递归

一棵二叉树的高度=Max(左孩子结点的高度, 右孩子结点的高度)+1，根据这个递推关系来写递归函数，首先能确定的是，一定是后序遍历的框架，因为我们要根据两个孩子推出父亲的结果，然后向上一层返回。对于叶子节点来说高度就为1，对于每个节点都选取左右子树高度最大的，返回时加上自己的高度1。

public int maxDepth(TreeNode root) {
    if(root == null) return 0;
    int leftMaxDepth = maxDepth(root.left);
    int rightMaxDepth = maxDepth(root.right);
    return Math.max(leftMaxDepth, rightMaxDepth)+1;
}

3.总结

二叉树的高度是一个基础的题目，对这个概念的理解有助于解决后面题目，后面在树的宽度、树的最小深度、平衡二叉树等，都会用到树的高度的概念。