精选50题之 104. 二叉树的最大深度

旧城等待， 2024-04-19 10:36 10阅读 0赞

### 腾讯精选练习（50 题）之 104. 二叉树的最大深度 ###

*   *  原题目链接
     *  直接实现
     *  其他方式

## [原题目链接][Link 1] ##

给定一个二叉树，找出其最大深度。  
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。  
说明: 叶子节点是指没有子节点的节点。

示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]

## 直接实现 ##

通过递归来解决，使用 DFS策略。

/**
     * 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)
                return 0;
            int Lmax = maxDepth(root->left);
            int Rmax = maxDepth(root->right);
            return Lmax > Rmax ? Lmax + 1 : Rmax + 1;
        }
    };

![在这里插入图片描述][20190918011203205.png]  
复杂度分析：

*  时间复杂度：O(N)
 *  空间复杂度：O(N) 最坏 / O(logN) 最好

## 其他方式 ##

一、使用栈实现DFS搜索

/**
     * 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)
                return 0;
            stack<pair<TreeNode*,int>>s;
            TreeNode* p = root;
            int MaxDepth = 0;
            int Depth = 0;
            while(!s.empty() || p)
            {
        
                while(p)
                {
        
                    s.push(pair<TreeNode*,int>(p, Depth+1));
                    Depth++;
                    p = p->left;
                }
                p = s.top().first;
                Depth = s.top().second;
                if(MaxDepth < Depth)
                    MaxDepth = Depth;
                s.pop();
                p = p->right;
            }
            return MaxDepth;
        }
    };

![在这里插入图片描述][20190918011936327.png]  
复杂度分析：

*  时间复杂度：O(N)
 *  空间复杂度：O(N)

二、使用队列实现BFS

int maxDepth(TreeNode* root) {
        
        deque<TreeNode*>q;
        reeNode* p;
        if(!root)return 0;
        q.push_back(root);
        int deep = 0;
        while(!q.empty())
        {
        
            deep++;
            int amo = q.size();
            while(amo>0)
            {
        
                p = q.front();
                q.pop_front();
                if(p->left)q.push_back(p->left);
                if(p->right)q.push_back(p->right);
                amo--;
            }
        }
        return deep;
    }

![在这里插入图片描述][20190918012612540.png]

[Link 1]: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3406952fbd474fb7b8fd501db28d2897.png
[20190918011203205.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/24e4c37415934974952d2f10b6178f6f.png
[20190918011936327.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1ef41a66c4384446b4dab9776e9ef886.png
[20190918012612540.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8dddbda1cfb14c7185c870d3b34c5b71.png