题解 | #二叉树的最大深度#

递归实现：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        // write code here
        if (root == nullptr) return 0;
        if (root->left == nullptr && root->right == nullptr) return 1;
        int ldepth = maxDepth(root->left);
        int rdepth = maxDepth(root->right);
        return 1 + max(ldepth, rdepth);
    }
};

BFS:

// BFS
class Solution {
public:
    int maxDepth(TreeNode* root) {
        // write code here
        if (root == nullptr) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int count = 0;
        while (!que.empty()) {
            int n = que.size();
            while (n--) {
                if(que.front()->left) que.push(que.front()->left);
                if(que.front()->right) que.push(que.front()->right);
                que.pop();
            }
            count++;
        }
        return count;
    }
};

DFS:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        // write code here
        if (root == nullptr) return 0;
        stack<TreeNode*> stk;  // 记录节点
        stack<int> level;  // 记录第几层
        stk.push(root);
        level.push(1);
        int count = 0;
        while (!stk.empty()) {
            TreeNode *node = stk.top();
            int tmp = level.top();
            stk.pop();
            level.pop();
            count = max(count, tmp);   // 记录最深层数
            if (node->left) {
                stk.push(node->left);
                level.push(tmp + 1);
            }
            if (node->right) {
                stk.push(node->right);
                level.push(tmp + 1);
            }
        }
        return count;
    }
};