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二叉树的最大深度的更多相关文章
-
[LeetCode] Maximum Depth of Binary Tree 二叉树的最大深度
Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the long ...
-
[LintCode] Maximum Depth of Binary Tree 二叉树的最大深度
Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the long ...
-
[LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度
Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the long ...
-
LeetCode 104. Maximum Depth of Binary Tree二叉树的最大深度 C++/Java
Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the long ...
-
[LeetCode] 104. Maximum Depth of Binary Tree ☆(二叉树的最大深度)
描述 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the l ...
-
【LeetCode】Maximum Depth of Binary Tree(二叉树的最大深度)
这道题是LeetCode里的第104道题. 给出题目: 给定一个二叉树,找出其最大深度. 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数. 说明: 叶子节点是指没有子节点的节点. 示例: 给定 ...
-
104 Maximum Depth of Binary Tree 二叉树的最大深度
给定一个二叉树,找出其最大深度.二叉树的深度为根节点到最远叶节点的最长路径上的节点数.案例:给出二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / ...
-
LeetCode——Maximum Depth of Binary Tree
LeetCode--Maximum Depth of Binary Tree Question Given a binary tree, find its maximum depth. The max ...
-
leetcode 104 Maximum Depth of Binary Tree二叉树求深度
Maximum Depth of Binary Tree Total Accepted: 63668 Total Submissions: 141121 My Submissions Question ...
随机推荐
-
Level2行情和传统行情的区别
序号 Level2行情 传统行情 Level 2特点 Level 2行情优势 1 每3秒钟发送一次行情信息 每6秒钟发送一次 行情显示速度更快 投资者更及时地获得交易信息 2 证券逐笔成交明细信息 证 ...
-
正确理解SQL Server的许可证(转)
今天在论坛上看到有人讨论如果使用SQL Server作为SEPM的后台数据库,需要多少个CAL的问题: If I do have to use SQL Server what type of li ...
-
Hibernate级联操作 注解
EJB3 支持的操作类型 /** * Cascade types (can override default EJB3 cascades */ public enum CascadeType { AL ...
-
SNMP: Simple? Network Management Protocol(转)
转自:http://www.rane.com/note161.html An SNMP Overview The Message Format The Actual Bytes Introductio ...
-
SqlServer查询数据库所有表
//SqlServer查询数据库所有表SELECT * FROM SYSOBJECTS WHERE TYPE='U' and name like '%dict%'
-
sqlserver 存储过程 带输出参数
CREATE PROCEDURE [dbo].[output] @acctNbr varchar(), --会员卡号 @acctPwd1 nvarchar() OUT, --登录密码 @acctPwd ...
-
左耳听风-ARTS-第3周(2019/4/7-2019/4/13)
Algorithm 本周的算法题是按顺序合并两个已排序的链表(https://leetcode.com/problems/merge-two-sorted-lists/).和归并排序的合并已排序数组的 ...
-
Kali学习笔记24:Nikto、Skipfish
文章的格式也许不是很好看,也没有什么合理的顺序 完全是想到什么写一些什么,但各个方面都涵盖到了 能耐下心看的朋友欢迎一起学习,大牛和杠精们请绕道 实验环境: Kali机器IP:192.168.163. ...
-
RDD PAPER
https://cs.stanford.edu/~matei/ https://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-12.pdf h ...
-
vbs习题
练习题: 1.输入3个数,输出其中最大的那个值. Option Explicit Dim intA,intB,intC intA=CInt(InputBox("请输入a:")) i ...