本题有多种解法:

  1. 后序遍历,每次返回以当前节点为根节点的子树的深度
  2. 先序遍历,记录根节点到当前节点的高度,如果是叶子,则更新max值

下面采用第一种思路:

class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        // write code here
        return postOrder(root);
    }

    int postOrder(TreeNode* root) {
        if (!root) return 0;
        int left = 1 + postOrder(root->left);
        int right = 1 + postOrder(root->right);
        return left > right ? left : right;
    }
};