104.二叉树的最大深度 (Easy)*

题目描述*

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例*

给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

代码*

递归 dfs 或 bfs。

递归 dfs迭代 dfsbfs

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

class Solution 
{
public:
    int maxDepth(TreeNode* root) 
    {
        if(root==NULL)return 0;
        int depth=0;
        int max=0;
        stack<pair<TreeNode*,int>> myStack;
        TreeNode*p=root;

        while(!myStack.empty()||p!=NULL)
        {
            while(p!=NULL)
            {
                myStack.push(pair<TreeNode*,int>(p,++depth));
                p=p->left;
            }
            p=myStack.top().first;
            depth=myStack.top().second;
            if(max<depth) max=depth;
            myStack.pop();
            p=p->right;
        }
        return max;
    }
};

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        int depth = 0;
        queue<TreeNode*> helpQueue;
        helpQueue.push(root);
        TreeNode *cur = root;
        while(!helpQueue.empty()) {
            int times = helpQueue.size();
            for(int i = 0; i < times; i++) {
                cur = helpQueue.front();
                helpQueue.pop();
                if(cur->left != nullptr) {
                    helpQueue.push(cur->left);
                }
                if(cur->right != nullptr) {
                    helpQueue.push(cur->right);
                }
            }
            depth++;
        }
        return depth;
    }
};

最后更新: July 23, 2022