leetcode 链接：剑指 Offer 55 - I. 二叉树的深度

题目

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

返回它的最大深度 3 。

解答 & 代码

dfs 后序遍历，先分别求得左右子树的最大深度，取较大值 + 1，就是以当前节点为根的树的最大深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 47.38% 的用户
内存消耗：18.4 MB, 在所有 C++ 提交中击败了 37.17% 的用户

改：稍微能加快运行
遇到叶子节点就直接返回 1，而不用去递归其为空的左右子树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        // 递归结束条件
        if(root == NULL)
            return 0;
        // 如果为叶子节点，直接返回 1（这一段不是必须的）
        if(root->left == NULL && root->right == NULL)
            return 1;
        // 后序遍历，先递归得到左右子树的最大深度
        // 取较大值 + 1，就是以当前节点为根的树的最大深度
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 80.69% 的用户
内存消耗：18.4 MB, 在所有 C++ 提交中击败了 38.88% 的用户