开一个二手车销售网站怎么做,普陀网站制作有哪些,网页游戏直接玩,网站视频插件代码本文章为结合leetcode题目以及公众号“代码随想录”的文章所做的笔记#xff01; 感觉代码随想录的题目整理真的很好#xff0c;比自己盲目刷题好很多。 目录1、二叉树小记1、满二叉树与完全二叉树2、二叉搜索树3、平衡二叉搜索树AVL4、二叉树存储方式5、二叉树遍历方式6、二… 本文章为结合leetcode题目以及公众号“代码随想录”的文章所做的笔记 感觉代码随想录的题目整理真的很好比自己盲目刷题好很多。 目录1、二叉树小记1、满二叉树与完全二叉树2、二叉搜索树3、平衡二叉搜索树AVL4、二叉树存储方式5、二叉树遍历方式6、二叉树的定义2、二叉树深度优先遍历递归算法书写1、leetcode144题2、leetcode145题3、leetcode94题3、二叉树深度优先遍历迭代算法书写1、先序遍历迭代法2、中序遍历迭代法3、后序遍历迭代法4、二叉树深度优先遍历迭代算法格式统一5、二叉树层序遍历1、leetcode102:二叉树的层序遍历2、leetcode107:二叉树的层序遍历 II3、leetcode199:二叉树的右视图4、leetcode637:二叉树的层平均值5、leetcode429:N叉树的层序遍历6、leetcode515. 在每个树行中找最大值7、leetcode116. 填充每个节点的下一个右侧节点指针8、leetcode117. 填充每个节点的下一个右侧节点指针 II遇上一题思路代码一致9、104. 二叉树的最大深度10、111. 二叉树的最大深度1、二叉树小记
1、满二叉树与完全二叉树
满二叉树深度为k有2的k-1个节点的二叉树。 完全二叉树除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层则该层包含1~2h个节点。
2、二叉搜索树
二叉搜索树是有数值的是一个有序树。 它的特点 1、若它的左子树不空则左子树所有结点的值均小于它根结点的值 2、若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 3、它的左右子树也分别为二叉排序树 3、平衡二叉搜索树AVL
AVL是一棵空数或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。 C中map、set、multimap、multiset的底层实现都是平衡二叉搜索树所以map、set的增删操作时间复杂度都是logn。 而unordered_map、unordered_set、unordered_map、unordered_map底层实现是哈希表。
4、二叉树存储方式
链表存储与数组存储。 数组存储二叉树遍历如果父节点的数组下标是i那么它的左孩子就是i21,右孩子就是i22.
5、二叉树遍历方式
有两种遍历方式 1、深度优先遍历先往深走遇到叶子结点再往回走 分为前序遍历、中序遍历、后序遍历 这里的前中后指的是中间结点的遍历顺序 前序遍历中、左、右 中序遍历左、中、右 后序遍历左、右、中 深度优先遍历使用递归是比较方便的可以借助栈使用非递归方式实现。
2、广度优先遍历一层一层的去遍历 分为层次遍历 广度优先遍历一般使用队列实现利用了队列的先进先出的特点。这样才能一层一层的来遍历二叉树。
6、二叉树的定义
二叉树的定义和链表差不多多了一个指针
struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x),left(NULL),right(NULL) {}
};2、二叉树深度优先遍历递归算法书写
递归算法的三个要素 1、确定递归函数的参数和返回值 若是在递归过程中需要处理某个参数就在递归函数里面加上这个参数。 明确每次递归地返回值是什么进而确定递归函数的返回类型 2、确定终止条件 1、如果在递归算法运行过程中出现栈溢出大概率是终止条件写的不对 2、操作系统也是用一个栈的结构来保存每一层递归地信息如果递归没有终止操作系统的内存栈必然就会溢出 3、确定单层递归逻辑 确定每一层递归需要处理的信息。在这里也会重复调用自己来实现递归地过程 以前序遍历为例 1、因为要打印出前序遍历结点的数值所以参数里需要传入vector放在结点里的数据。没有返回值
void traversal(TreeNode* cur ,vectorint vec)2、在递归过程中如何算是递归结束如果当前遍历的结点是空的那么本层递归就结束了
if(cur NULL) return;3、前序遍历是中左右的循序所以在单层递归中就要先取出中结点的数据
vec.push_back(cur-val); //中
traversal(cur-left,vec); //左
traversal(cur-right,vec); //右完整代码:
class Solution{public:void traversal(TreeNode* cur , vectorint vec){if(cur NULL) return;vec.push_back(cur-val);traversal(cur-left,vec);traversal(cur-right,vec);}vectorint preorderTraversal(TreeNode* root){vectorint result;traversal(root,result);return result;}
};中序遍历
void traversal(TreeNode* cur , vectorint vec)
{if(cur NULL) return;traversal(cur-left,vec);vec.push_back(cur-val);traversal(cur-right,vec);
}后序遍历
void traversal(TreeNode* cur , vectorint vec)
{if(cur NULL) return;traversal(cur-left,vec);traversal(cur-right,vec);vec.push_back(cur-val);
}1、leetcode144题
给定一个二叉树返回它的 前序 遍历。 示例: 输入: [1,null,2,3] 1 2 / 3 输出: [1,2,3]
/*** 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:void traversal(TreeNode* cur , vectorint vec){if(cur NULL) return;vec.push_back(cur-val);traversal(cur-left,vec);traversal(cur-right,vec);}vectorint preorderTraversal(TreeNode* root){vectorint result;traversal(root,result);return result;}
};2、leetcode145题
给定一个二叉树返回它的 后序 遍历。 示例: 输入: [1,null,2,3] 1 2 / 3 输出: [3,2,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:void traversal(TreeNode* cur , vectorint vec){if(cur NULL) return;traversal(cur-left,vec);traversal(cur-right,vec);vec.push_back(cur-val);}vectorint postorderTraversal(TreeNode* root) {vectorint result;traversal(root,result);return result;}
};3、leetcode94题
/*** 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:void traversal(TreeNode* cur , vectorint vec){if(cur NULL) return;traversal(cur-left,vec);vec.push_back(cur-val);traversal(cur-right,vec);}vectorint inorderTraversal(TreeNode* root) {vectorint result;traversal(root,result);return result;}
};3、二叉树深度优先遍历迭代算法书写
原理为什么可以使用迭代法(非递归地方式)来实现二叉树的前后中序遍历 递归地实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中 然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因。
1、先序遍历迭代法
前序遍历中左右每次处理的是中间结点先将根结点放入栈中然后将右孩子放入栈中再加入左孩子。 为什么要先加入有孩子再加入左孩子 这样出栈的时候才是中左右的顺序。 顺序如下
class Solution{
public:vectorint preorderTraversal(TreeNode* root){stackTreeNode* st; //构建一个栈vectorint result;st.push(root); //先将根结点压入栈中while(!st.empty()){ //当栈中还有元素时TreeNode* node st.top(); //将栈顶元素赋给新结点 st.pop(); //将栈顶元素出栈if(node !NULL) result.push_back(node-val); //如果这个结点不为空将值赋给resultelse continue; //否则继续也就是说如果结点为空不赋值st.push(node-right); //将该中结点的右孩子压入栈中st.push(node-left); //将该结点中的左孩子压入栈中}return result;}
};2、中序遍历迭代法
注意前序遍历的迭代法思路不能直接套用到中序遍历上。 在迭代的过程中有两个操作: 1、【处理】将元素放入result数组 2、【访问】遍历结点 前序遍历中遍历的顺序是中左右。 先访问中间结点先处理中间结点 要访问的元素和要处理的元素的顺序一致都是中间结点。 而中序遍历遍历顺序为左中右。 先访问二叉树顶部结点然后一层一层向下访问直到到达树左面的最底部再开始处理结点再把结点的数值放到result数组中 这就导致了处理顺序和访问顺序不一致 所以在使用迭代 法时需要借用指针的遍历来帮助访问结点使用栈来处理结点上的元素。
class Solution{
public:vectorint inorderTraversal(TreeNode* root){vectorint result;stackTreeNode* st;TreeNode* cur root;while(!st.empty() || cur!NULL){if(cur!NULL){st.push(cur);cur cur-left; //先一直都是从左结点深入直到某一个结点的左孩子为NULL}//如果该点是父结点的左孩子且指向空则将cur指向它的父结点为最深的左结点然后将父结点出栈将值赋给结果数组再将指针指向此父结点的右孩子这样保证了左中右的遍历顺序else{cur st.top();st.pop();result.push_back(cur-val);cur cur-right;} }return result;}
};3、后序遍历迭代法
后序遍历左右中。 先序遍历中左右。 我们只需要调整一下先序遍历的代码顺序变为中右左的遍历顺序。 然后反转result数组输出结果就是左右中。
/*** 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:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st; //构建一个栈vectorint result;st.push(root); //先将根结点压入栈中while(!st.empty()){ //当栈中还有元素时TreeNode* node st.top(); //将栈顶元素赋给新结点 st.pop(); //将栈顶元素出栈if(node !NULL) result.push_back(node-val); //如果这个结点不为空将值赋给resultelse continue; //否则继续也就是说如果结点为空不赋值st.push(node-left); //将该中结点的左孩子压入栈中st.push(node-right); //将该结点中的右孩子压入栈中}//反转resultreverse(result.begin(),result.end());return result;}
};4、二叉树深度优先遍历迭代算法格式统一
之前迭代法例子中提到无法同时解决访问节点遍历和处理结点将结点放入结果不一致的情况。 解决方法 将访问的结点放入栈中把要处理的结点也放入栈中但是要做标记 标记方法将要处理的结点放入栈中之后紧接着放入一个空指针作为标记 将访问的结点直接加入到栈中但是如果是处理的结点则后面放入一个空结点这样只有空结点弹出的时候才将下一个结点放进结果集。 如何知道该访问的结点是我们需要处理的结点中结点是我们需要处理的结点所以只需要在中结点后面加入一个空结点就行了 中序遍历
class Solution{
public:vectorint inorderTraversal(TreeNode* root){vectorint result;stackTreeNode* st;if(root !NULL) st.push(root);while(!st.empty()){TreeNode* node st.top(); //标记操作直到遇到NULLif(node!NULL){//将该结点弹出避免重复操作st.pop();//添加右结点if(node-right) st.push(node-right);//添加中结点st.push(node);//标记st.push(NULL); //添加左结点if(node-left) st.push(node-left);}//只有遇到空结点的时候才将下一个结点放入到结果中else{//弹出空结点st.pop();node st.top();st.pop(); result.push_back(node-val);}}return result;}
};先序遍历中左右
class Solution{
public:vectorint preorderTraversal(TreeNode* root){vectorint result;stackTreeNode* st;if(root !NULL) st.push(root);while(!st.empty()){TreeNode* node st.top(); //标记操作直到遇到NULLif(node!NULL){//将该结点弹出避免重复操作st.pop();//添加右结点if(node-right) st.push(node-right);//添加左结点if(node-left) st.push(node-left);//添加中结点st.push(node);//标记st.push(NULL); }//只有遇到空结点的时候才将下一个结点放入到结果中else{//弹出空结点st.pop();node st.top();st.pop(); result.push_back(node-val);}}return result;}
};后序遍历左右中
class Solution{
public:vectorint postorderTraversal(TreeNode* root){vectorint result;stackTreeNode* st;if(root !NULL) st.push(root);while(!st.empty()){TreeNode* node st.top(); //标记操作直到遇到NULLif(node!NULL){//将该结点弹出避免重复操作st.pop();//添加中结点st.push(node);//标记st.push(NULL); //添加右结点if(node-right) st.push(node-right);//添加左结点if(node-left) st.push(node-left);}//只有遇到空结点的时候才将下一个结点放入到结果中else{//弹出空结点st.pop();node st.top();st.pop(); result.push_back(node-val);}}return result;}
};总结 这种方法比较好记忆主要注意以下几点 1、栈的特性入栈和出栈相反所以如果想输出顺序为“左中右”入栈顺序必须为“右中左” 2、入栈的处理可以将整个树简化为3个结点一组的多个子树。每次循环处理的实际就是将这样的3个结点按照规定的顺序进行入栈。 3、NULL结点的加入以及出栈规则的指定 以中序遍历为例保证了当左孩子作为栈顶元素时不会立即出栈而是会将当前的左孩子(栈顶元素)作为下次遍历的父结点接着按照规则顺序入栈直到当前的左孩子作为父结点再无孩子时此时是入栈规则为父结点、NULL结点遇到NULL结点进行出栈。 5、二叉树层序遍历
1、leetcode102:二叉树的层序遍历
给你一个二叉树请你返回其按 层序遍历 得到的节点值。 即逐层地从左到右访问所有节点。 示例 二叉树[3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其层次遍历结果
[ [3], [9,20], [15,7] ] 思考 借用队列来实现【队列先进先出符合一层一层遍历的逻辑】 而栈先进后出适合模拟深度优先遍历也就是递归地逻辑。 【这种层序遍历的方式就是图论中的广度优先遍历只不过用在了二叉树上】 思考
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;if(root!NULL) que.push(root);vectorvectorint result;while(!que.empty()){//该层结点元素个数 该层队列元素int size que.size();vectorint vec;//这里要使用固定大小的size不能使用que.size(),因为在处理中que.size是不断变化的//将这层元素送入队列中并依次从队首向队尾将元素出队列每个元素出队列的同时又将其不为空的子结点送入队列for(int i 0;isize;i){TreeNode* node que.front();//将队首元素送入该层结果que.pop();vec.push_back(node-val);//将左右孩子结点入队列作为下一层的元素if(node-left) que.push(node-left);if(node-right) que.push(node-right);}result.push_back(vec);}return result;}
};2、leetcode107:二叉树的层序遍历 II
给定一个二叉树返回其节点值自底向上的层次遍历。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历 例如 给定二叉树 [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其自底向上的层次遍历为
[ [15,7], [9,20], [3] ] 思路在层序遍历的基础上进行直接反转
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {queueTreeNode* que;if(root!NULL) que.push(root);vectorvectorint result;while(!que.empty()){//该层结点元素个数 该层队列元素int size que.size();vectorint vec;//这里要使用固定大小的size不能使用que.size(),因为在处理中que.size是不断变化的//将这层元素送入队列中并依次从队首向队尾将元素出队列每个元素出队列的同时又将其不为空的子结点送入队列for(int i 0;isize;i){TreeNode* node que.front();//将队首元素送入该层结果que.pop();vec.push_back(node-val);//将左右孩子结点入队列作为下一层的元素if(node-left) que.push(node-left);if(node-right) que.push(node-right);}result.push_back(vec);}//将层序遍历反转一下结果reverse(result.begin(),result.end());return result;}
};3、leetcode199:二叉树的右视图
给定一棵二叉树想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释: 1 — / 2 3 — \ 5 4 — 思路对层序遍历的的结果的每个子层result取最后的一个作为结果返回。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vectorint rightSideView(TreeNode* root) {queueTreeNode* que;if(root!NULL) que.push(root);vectorint realresult;while(!que.empty()){//该层结点元素个数 该层队列元素int size que.size();vectorint vec;//这里要使用固定大小的size不能使用que.size(),因为在处理中que.size是不断变化的//将这层元素送入队列中并依次从队首向队尾将元素出队列每个元素出队列的同时又将其不为空的子结点送入队列for(int i 0;isize;i){TreeNode* node que.front();//将队首元素送入该层结果que.pop();vec.push_back(node-val);//将左右孩子结点入队列作为下一层的元素if(node-left) que.push(node-left);if(node-right) que.push(node-right);}realresult.push_back(vec[size-1]);}return realresult;}
};4、leetcode637:二叉树的层平均值
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。 示例 1 输入 3 / 9 20 / 15 7 输出[3, 14.5, 11] 解释 第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。 提示 节点值的范围在32位有符号整数范围内。
思考层序遍历中加入累加以及求均值操作
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vectordouble averageOfLevels(TreeNode* root) {queueTreeNode* que;if(root!NULL) que.push(root);vectordouble realresult;while(!que.empty()){//该层结点元素个数 该层队列元素int size que.size();vectorint vec;double sum 0;//这里要使用固定大小的size不能使用que.size(),因为在处理中que.size是不断变化的//将这层元素送入队列中并依次从队首向队尾将元素出队列每个元素出队列的同时又将其不为空的子结点送入队列for(int i 0;isize;i){TreeNode* node que.front();//将队首元素送入该层结果que.pop();vec.push_back(node-val);sumvec[i];//将左右孩子结点入队列作为下一层的元素if(node-left) que.push(node-left);if(node-right) que.push(node-right);}realresult.push_back(sum /size);}return realresult;}
};5、leetcode429:N叉树的层序遍历
给定一个 N 叉树返回其节点值的层序遍历。 (即从左到右逐层遍历)。 例如给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明: 树的深度不会超过 1000。 树的节点总数不会超过 5000。 思考与二叉树层序遍历方法一样不过子结点的个数不定
/*
// Definition for a Node.
class Node {
public:int val;vectorNode* children;Node() {}Node(int _val) {val _val;}Node(int _val, vectorNode* _children) {val _val;children _children;}
};
*/class Solution {
public:vectorvectorint levelOrder(Node* root) {queueNode* que;if(root!NULL) que.push(root);vectorvectorint result;while(!que.empty()){//该层结点元素个数 该层队列元素int size que.size();vectorint vec;//这里要使用固定大小的size不能使用que.size(),因为在处理中que.size是不断变化的//将这层元素送入队列中并依次从队首向队尾将元素出队列每个元素出队列的同时又将其不为空的子结点送入队列for(int i 0;isize;i){Node* node que.front();//将队首元素送入该层结果que.pop();vec.push_back(node-val);//将所有孩子结点入队列作为下一层的元素for(int j0;jnode-children.size();j){if(node-children[j]) que.push(node-children[j]);}}result.push_back(vec);}return result;}
};6、leetcode515. 在每个树行中找最大值
您需要在二叉树的每一行中找到最大的值。 示例 输入: 1 / 3 2 / \ \ 5 3 9
输出: [1, 3, 9] 思考层序遍历然后在每层中找最大值
/*** 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:vectorint largestValues(TreeNode* root) {queueTreeNode* que;if(root!NULL) que.push(root);vectorint result;while(!que.empty()){//该层结点元素个数 该层队列元素int size que.size();int max-2147483648; //(最小值)vectorint vec;//这里要使用固定大小的size不能使用que.size(),因为在处理中que.size是不断变化的//将这层元素送入队列中并依次从队首向队尾将元素出队列每个元素出队列的同时又将其不为空的子结点送入队列for(int i 0;isize;i){TreeNode* node que.front();//将队首元素送入该层结果que.pop();vec.push_back(node-val);if(maxnode-val) max node-val;//将左右孩子结点入队列作为下一层的元素if(node-left) que.push(node-left);if(node-right) que.push(node-right);}result.push_back(max);}return result;}
};7、leetcode116. 填充每个节点的下一个右侧节点指针
给定一个完美二叉树其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。 初始状态下所有 next 指针都被设置为 NULL。
示例 解释给定二叉树如图 A 所示你的函数应该填充它的每个 next 指针以指向其下一个右侧节点如图 B 所示。 提示 你只能使用常量级额外空间。 使用递归解题也符合要求本题中递归程序占用的栈空间不算做额外的空间复杂度。
思考层序遍历只不过在单层遍历的时候记录本层的头部节点然后在遍历的时候让前一个节点指向本节点。
/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};
*/class Solution {
public:Node* connect(Node* root) {queueNode* que;if(root!NULL) que.push(root);while(!que.empty()){int size que.size();Node* node;Node* Prenode;for(int i 0;isize;i){//每层第一个元素元素if(i0){Prenode que.front();que.pop();node Prenode;}//非每层第一个结点else{node que.front();que.pop();//将此结点与上一个结点连在一起Prenode-next node;Prenode node; }//将左右孩子结点入队列作为下一层的元素if(node-left) que.push(node-left);if(node-right) que.push(node-right);}Prenode-next NULL;}return root;}
};8、leetcode117. 填充每个节点的下一个右侧节点指针 II遇上一题思路代码一致
给定一个二叉树 struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。 初始状态下所有 next 指针都被设置为 NULL。
进阶 你只能使用常量级额外空间。 使用递归解题也符合要求本题中递归程序占用的栈空间不算做额外的空间复杂度。
9、104. 二叉树的最大深度
思路层序遍历每层对一个变量即可 给定一个二叉树找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例 给定二叉树 [3,9,20,null,null,15,7]
3/ 9 20 / 15 7 返回它的最大深度 3 。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {queueTreeNode* que;if(root!NULL) que.push(root);int result0;while(!que.empty()){//该层结点元素个数 该层队列元素int size que.size();//这里要使用固定大小的size不能使用que.size(),因为在处理中que.size是不断变化的//将这层元素送入队列中并依次从队首向队尾将元素出队列每个元素出队列的同时又将其不为空的子结点送入队列for(int i 0;isize;i){TreeNode* node que.front();//将队首元素送入该层结果que.pop();//将左右孩子结点入队列作为下一层的元素if(node-left) que.push(node-left);if(node-right) que.push(node-right);}result;}return result; }
};10、111. 二叉树的最大深度
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3/ 9 20 / 15 7 返回它的最小深度 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 minDepth(TreeNode* root) {queueTreeNode* que;if(root!NULL) que.push(root);int result0;int break_flag0;while(!que.empty()){//该层结点元素个数 该层队列元素int size que.size();//这里要使用固定大小的size不能使用que.size(),因为在处理中que.size是不断变化的//将这层元素送入队列中并依次从队首向队尾将元素出队列每个元素出队列的同时又将其不为空的子结点送入队列for(int i 0;isize;i){TreeNode* node que.front();//将队首元素送入该层结果que.pop();if(!node-left !node-right){return result1;} //将左右孩子结点入队列作为下一层的元素if(node-left) que.push(node-left);if(node-right) que.push(node-right);}result;}return result; }
};
