力扣-104题二叉树的最大深度（C++）- 递归+迭代

怼烎@ 2022-08-31 07:24 150阅读 0赞

题目链接：[https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/][https_leetcode-cn.com_problems_maximum-depth-of-binary-tree]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
解法一：递归

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        int maxDepth(TreeNode* root) {
        
            return dfs(root);
        }
    
    	//思路：先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值再+1
        //+1是因为算上当前中间节点，即当前节点为根的树的深度
        int dfs(TreeNode* root){
        //求高度，每次求左右节点高度的最大值
            if(root==NULL) return 0;
    
            int left=dfs(root->left);
            int right=dfs(root->right);
    
            return (left>right?left:right)+1;
        }
    };

解法二：迭代

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        int maxDepth(TreeNode* root) {
        
            //思路：层序遍历二叉树的深度就是该二叉树的最大深度
            int depth=0;
            if(root==NULL) return depth;
            
            queue<TreeNode*> que;
            que.push(root);
    
            while(!que.empty()){
        
                int size=que.size();
                depth++;
    
                while(size--){
        
                    TreeNode* node=que.front();
                    que.pop();
    
                    if(node->left) que.push(node->left);
                    if(node->right) que.push(node->right);
                }
    
            }
            return depth;
        }
    };

[https_leetcode-cn.com_problems_maximum-depth-of-binary-tree]: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/b8798f2aa78b4c1ebaff552ee3391273.png