104. 二叉树的最大深度

题目链接

解题思路

• 普通的递归可能很简单，但是，现在要求，使用「二叉树递归套路」来思考问题
• 每个节点需要什么信息？如果根节点，能够有一个「最大深度」的信息，那么直接返回就可以了。那么，这个信息可以通过左子树信息 + 右子树信息 得到吗？
• max(左子树最大深度, 右子树最大深度) + 1，就是该节点的最大深度，所以是能够得到的。
• 所以，每个节点需要的信息就一个：1️⃣以该节点为头的最大深度是多少

代码

class Solution {
public:

    // 以head为头，最大深度是多少？
    // 因为就需要一个信息，所以不需要使用一个结构体来保存信息了
    int process(TreeNode* head) {
        if (head == nullptr) {
            return 0;
        }
        int left_info = process(head->left);
        int right_info = process(head->right);
        return max(left_info, right_info) + 1;
    }
    int maxDepth(TreeNode* root) {
        return process(root);
    }
};