[Leetcode] Maximum depth of binary tree二叉树的最大深度

时间:2022-08-31 18:39:09

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

方法一:

层次遍历,整棵树的层数,即二叉树的最大深度。主体的代码还是在层次遍历的基础上改成的。

/**
* Definition for binary tree
* 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==NULL) return ;
int level=;
queue<TreeNode *> Q;
Q.push(root);
while( !Q.empty())
{
int levNum=;
int count=Q.size(); //不能和下面的while条件写成levNUm<Q.size()
                    //因为这样写以后,不遍历完整棵树,不会跳出
while(levNum<count)
{
TreeNode *temp=Q.front();
Q.pop();
if(temp->left)
Q.push(temp->left);
if(temp->right)
Q.push(temp->right);
levNum++;
}
level++;
}
return level;
}
};

方法二:

写法不一样,思想一样。

class Solution
{
public:
int maxDepth(TreeNode* root)
{
if(!root) return ;
queue<TreeNode*> Q; int nCount=; //某一层节点的个数
int nDepth=; //层数 //基于BFS,引入两个计数器
Q.push(root);
while(!Q.empty())
{
TreeNode* pCur=Q.front();
Q.pop();
nCount--; if(pCur->left)
Q.push(pCur->left);
if(pCur->right)
Q.push(pCur->right); if(!nCount) //保证遍历某一层时,深度不增加
{
nDepth++;
nCount=Q.size();
}
}
return nDepth;
}
}

方法三:

递归算法,终止条件为:节点不存在时,返回0,递归式为1+max(maxDepth(root->left),maxDepth(too->right)),即左右子树中的最大深度加上root所在层。

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

[Leetcode] Maximum depth of binary tree二叉树的最大深度的更多相关文章

  1. &lbrack;LeetCode&rsqb; Maximum Depth of Binary Tree 二叉树的最大深度

    Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the long ...

  2. &lbrack;LintCode&rsqb; Maximum Depth of Binary Tree 二叉树的最大深度

    Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the long ...

  3. &lbrack;LeetCode&rsqb; 104&period; Maximum Depth of Binary Tree 二叉树的最大深度

    Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the long ...

  4. LeetCode 104&period; Maximum Depth of Binary Tree二叉树的最大深度 C&plus;&plus;&sol;Java

    Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the long ...

  5. &lbrack;LeetCode&rsqb; 104&period; Maximum Depth of Binary Tree &star;&lpar;二叉树的最大深度&rpar;

    描述 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the l ...

  6. 【LeetCode】Maximum Depth of Binary Tree&lpar;二叉树的最大深度&rpar;

    这道题是LeetCode里的第104道题. 给出题目: 给定一个二叉树,找出其最大深度. 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数. 说明: 叶子节点是指没有子节点的节点. 示例: 给定 ...

  7. 104 Maximum Depth of Binary Tree 二叉树的最大深度

    给定一个二叉树,找出其最大深度.二叉树的深度为根节点到最远叶节点的最长路径上的节点数.案例:给出二叉树 [3,9,20,null,null,15,7],    3   / \  9  20    /  ...

  8. LeetCode——Maximum Depth of Binary Tree

    LeetCode--Maximum Depth of Binary Tree Question Given a binary tree, find its maximum depth. The max ...

  9. leetcode 104 Maximum Depth of Binary Tree二叉树求深度

    Maximum Depth of Binary Tree Total Accepted: 63668 Total Submissions: 141121 My Submissions Question ...

随机推荐

  1. Level2行情和传统行情的区别

    序号 Level2行情 传统行情 Level 2特点 Level 2行情优势 1 每3秒钟发送一次行情信息 每6秒钟发送一次 行情显示速度更快 投资者更及时地获得交易信息 2 证券逐笔成交明细信息 证 ...

  2. 正确理解SQL Server的许可证&lpar;转&rpar;

    今天在论坛上看到有人讨论如果使用SQL Server作为SEPM的后台数据库,需要多少个CAL的问题:   If I do have to use SQL Server what type of li ...

  3. Hibernate级联操作 注解

    EJB3 支持的操作类型 /** * Cascade types (can override default EJB3 cascades */ public enum CascadeType { AL ...

  4. SNMP&colon; Simple&quest; Network Management Protocol(转)

    转自:http://www.rane.com/note161.html An SNMP Overview The Message Format The Actual Bytes Introductio ...

  5. SqlServer查询数据库所有表

    //SqlServer查询数据库所有表SELECT * FROM SYSOBJECTS WHERE TYPE='U' and name like '%dict%'

  6. sqlserver 存储过程 带输出参数

    CREATE PROCEDURE [dbo].[output] @acctNbr varchar(), --会员卡号 @acctPwd1 nvarchar() OUT, --登录密码 @acctPwd ...

  7. 左耳听风-ARTS-第3周(2019&sol;4&sol;7-2019&sol;4&sol;13)

    Algorithm 本周的算法题是按顺序合并两个已排序的链表(https://leetcode.com/problems/merge-two-sorted-lists/).和归并排序的合并已排序数组的 ...

  8. Kali学习笔记24:Nikto、Skipfish

    文章的格式也许不是很好看,也没有什么合理的顺序 完全是想到什么写一些什么,但各个方面都涵盖到了 能耐下心看的朋友欢迎一起学习,大牛和杠精们请绕道 实验环境: Kali机器IP:192.168.163. ...

  9. RDD PAPER

    https://cs.stanford.edu/~matei/ https://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-12.pdf h ...

  10. vbs习题

    练习题: 1.输入3个数,输出其中最大的那个值. Option Explicit Dim intA,intB,intC intA=CInt(InputBox("请输入a:")) i ...