当前位置：首页 > article >正文

【LeetCode】LCR 175.计算二叉树的深度

article 2024/12/27 6:49:13

题目链接：

LCR 175.计算二叉树的深度

题目描述：

在这里插入图片描述

思路一（深度优先搜索）：

使用深度优先搜索算法进行二叉树后序遍历

复杂度分析：

时间复杂度 O(N)：N 为树的节点数量，计算树的深度需要遍历所有节点
空间复杂度 O(N): 最差情况下（当树退化为链表时），递归深度可达到 N

/**
 * 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 calculateDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        return max(calculateDepth(root->left),calculateDepth(root->right))+1;
    }
};

思路二（广度优先搜索算法）：

使用二叉树的层序遍历算法实现

复杂度分析：

时间复杂度 O(N) ： N 为树的节点数量，计算树的深度需要遍历所有节点。
空间复杂度 O(N) ：最差情况下（当树平衡时），队列 queue 同时存储 N/2 个节点。

/**
 * 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 calculateDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        vector<TreeNode*> queue;
        queue.push_back(root);
        int res = 0;

        while(!queue.empty()){
            res++;
            int n = queue.size();
            for(int i =0; i<n; i++){
                TreeNode* node = queue.front(); 
                queue.erase(queue.begin());
                if(node ->left != nullptr) queue.push_back(node ->left);
                if(node ->right != nullptr) queue.push_back(node ->right);
            }
        }

        return res;
    }
};