你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

【每日一题041】leetcode-104

2021-11-24 7:34:42

目录

  • 题目
  • 思路
  • 相关思考
  • 代码(C++)
  • 代码(C++/力扣)
  • 代码(C++/力扣)

题目

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

思路

1.递归求解,树高等于左子树右子树中的较高的一棵加1
2.1层次遍历,通过对size()的记录实现每一层遍历
2.2层次遍历,使用prenum和num来记录上一层的节点数和当前遍历层的节点数

相关思考

一开始没有考虑每一层加一,而是每入一次while循环加一,所以得出的并不是层数,而是节点数。

代码(C++)

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

    }
};

代码(C++/力扣)

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

代码(C++/力扣)

public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int preCount = 1;
        int pCount = 0;

        int level = 0;

        while (!q.isEmpty()) {
            TreeNode temp = q.poll();
            preCount--;

            if (temp.left != null) {
                q.offer(temp.left);
                pCount++;
            }
            if (temp.right != null) {
                q.offer(temp.right);
                pCount++;
            }

            if (preCount == 0) {
                preCount = pCount;
                pCount = 0;
                // System.out.println();
                level++;
            }
        }
        return level;
    }