网站公司缺点,权威发布封面,一流高职院校建设计划项目网站,网站开发有什么点子1.二叉树理论基础
二叉树的种类#xff1a;
满二叉树#xff1a;一棵二叉树只有度为0的结点和度为2的结点#xff0c;并且度为0的结点在同一层上#xff0c;则这棵二叉树为满二叉树。深度为k#xff0c;总共有2的k次幂-1个节点。
完全二叉树#xff1a;在完全二叉树中…1.二叉树理论基础
二叉树的种类
满二叉树一棵二叉树只有度为0的结点和度为2的结点并且度为0的结点在同一层上则这棵二叉树为满二叉树。深度为k总共有2的k次幂-1个节点。
完全二叉树在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层h从1开始则该层包含 1~ 2^(h-1) 个节点。优先级队列其实是一个堆堆就是一棵完全二叉树同时保证父子节点的顺序关系。
二叉搜索树二叉搜索树是一个有序树 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树 平衡二叉搜索树它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。C中map、set、multimapmultiset的底层实现都是平衡二叉搜索树map、set的增删操作时间时间复杂度是logn。
二叉树的存储方式链式存储指针连续或者顺序存储数组节点串联
链式存储需要有节点元素左指针左孩子和右指针右孩子左指针需要指向左边的子树右指针指向右边的子树根据节点的指针来实现的一般采用的
顺序存储数组存储二叉树数组更像是层序遍历之后的元素集合如果父节点的数组下标是 i那么它的左孩子就是 i * 2 1右孩子就是 i * 2 2。
二叉树的遍历方式
深度优先遍历先往深走遇到叶子节点再往回走。
前序遍历递归法迭代法
中序遍历递归法迭代法
后序遍历递归法迭代法
广度优先遍历一层一层的去遍历。
层次遍历迭代法 这两种遍历是图论中最基本的两种遍历方式。
前序遍历中左右
中序遍历左中右
后序遍历左右中
这里前中后指的是中间节点的位置左指的是左子树右指的是右子树子树也要实现相应的遍历顺序
栈其实就是递归的一种实现结构深度优先遍历可以使用栈来迭代完成广度优先遍历一般使用队列迭代实现完成
二叉树的定义链式存储
struct treenode{int val;treenode *left;treenode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
其实和链表的定义方式差不多比链表多一个指针指向左孩子右孩子 。
2.二叉树的递归遍历
递归做法三部曲
确定递归函数的参数和返回值我们要传进来什么样的参数确定终止条件确定什么时候递归结束避免栈错误出现确定单层递归逻辑确认每一层递归需要处理的信息
例如leetcode上的二叉树的前序遍历144题使用递归三部曲来解决
class Solution {
public://用递归方法实现的前序遍历void traversal(TreeNode* cur,vectorint vec){//三部曲1.确定参数和返回值需要传入节点和数组if(cur NULL){//三部曲2.确定终止条件遇到叶片节点返回return;}//三部曲3.确定单层递归的逻辑vec.push_back(cur-val);//中间节点traversal(cur-left,vec);//左子树traversal(cur-right,vec);//右子树}vectorint preorderTraversal(TreeNode* root) {//实现的函数vectorintresult;//定义一个数组去接收遍历的元素traversal(root,result);//我们需要把根节点和数组传入函数即可实现return result;}
};
接下来是二叉树的后序遍历145题
class Solution {
public:
//用递归方法实现的后序遍历//三部曲1.确定参数和返回值需要传入节点和数组void traversal(TreeNode* cur,vectorint vec){//三部曲2.确定终止条件遇到叶片节点返回if(cur NULL){return;}//三部曲3.确定单层递归的逻辑traversal(cur-left,vec);//左子树traversal(cur-right,vec);//右子树vec.push_back(cur-val);//中间节点}vectorint postorderTraversal(TreeNode* root) {vectorintresult;//定义一个数组去接收遍历的元素traversal(root,result);//我们需要把根节点和数组传入函数即可实现return result;}
};
下面是二叉树的中序遍历94题
class Solution {
public:
//用递归方法实现的中序遍历//三部曲1.确定参数和返回值需要传入节点和数组void traversal(TreeNode* cur,vectorint vec){//三部曲2.确定终止条件遇到叶片节点返回if(cur NULL){return;}//三部曲3.确定单层递归的逻辑traversal(cur-left,vec);//左子树vec.push_back(cur-val);//中间节点traversal(cur-right,vec);//右子树}vectorint inorderTraversal(TreeNode* root) {vectorintresult;//定义一个数组去接收遍历的元素traversal(root,result);//我们需要把根节点和数组传入函数即可实现return result;}
};
3.二叉树的迭代遍历
递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中所以我们采用栈来实现递归的二叉树前中后序遍历。
前序遍历迭代法定义一个栈先将根节点传进去注意栈的类型直到栈为空先将右节点放进去在把左节点放进去。因为栈的特性先进后出前序遍历是中左右的顺序所以需要先把右子树根节点压进去之后在处理再把左子树根节点压入处理。
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode*st;//定义一个栈去实现递归操作指定树指针vectorintresult;//结果数组集if(root NULL)return result;//如果根节点为空直接返回st.push(root);//把根节点压入栈中//栈里的元素没空就继续执行知道全为空为止while(!st.empty()){TreeNode* node st.top();//树节点就是栈顶元素st.pop();//弹出栈顶元素result.push_back(node-val);//放到结果数组当中if(node-right)st.push(node-right);//先放入右节点因为弹出的时候是先进后出if(node-left)st.push(node-left);//先处理左节点}return result;}
};
后序遍历迭代法也是需要定义一个栈因为前序遍历是中左右后序遍历的顺序是左右中我们将顺序调换中右左在反转一下数组即可得到后序遍历
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode*st;//定义一个栈注意栈里数据类型是树的指针vectorintresult;//结果if(root NULL)return result;//注意要判断st.push(root);//先将根节点指针压入建立联系//循环语句处理栈不为空就处理while(!st.empty()){//栈顶元素定义当前指针TreeNode* node st.top();st.pop();//然后弹出指针result.push_back(node-val);//将这个值放入数组if(node-left)st.push(node-left);//注先放左子树后方右子树if(node-right)st.push(node-right);}reverse(result.begin(),result.end());//反转一下数组即可return result;}
};
中序遍历迭代法之前前序后序遍历都是先处理元素放入数组在遍历节点访问元素和处理元素顺序一致中间节点中序遍历是左中右的顺序先访问根节点在一层一层向下访问到达最左面叶片节点处理节点
中序遍历需要指针遍历来访问节点栈来处理元素
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {stackTreeNode*st;//定义一个栈vectorintresult;//结果//if(root NULL)return result;TreeNode* cur root;//当前指针是用来访问最左侧的叶片节点指针指向根节点//循环条件栈不为空while(cur!NULL||!st.empty()){//访问最左侧的叶片节点if(cur!NULL){st.push(cur);//将访问的节点放入栈中cur cur-left;//找左}else{cur st.top();//放入元素栈顶st.pop();//弹出result.push_back(cur-val);//把这个值放入结果且现在中间节点cur cur-right;//访问右侧节点}}return result;}
};
前序后序节点改变一下顺序就可以实现中序遍历不可以
4.二叉树的统一迭代法
将访问的节点放入栈中把要处理的节点也放入栈中但是要做标记就是要处理的节点放入栈之后紧接着放入一个空指针作为标记。 中序遍历使用统一迭代法来实现
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {stackTreeNode*st;vectorintresult;if(root ! NULL)st.push(root);//加入根节点//循环条件while(!st.empty()){TreeNode* node st.top();//指针指向根节点//节点不为空就加入遇到空节点加入结果集if(node ! NULL){st.pop();//避免多操作if(node-right)st.push(node-right);//右st.push(node);//中st.push(NULL);//访问过没做处理使用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) {stackTreeNode*st;vectorintresult;if(root ! NULL)st.push(root);//加入根节点//循环条件while(!st.empty()){TreeNode* node st.top();//指针指向根节点//节点不为空就加入遇到空节点加入结果集if(node ! NULL){st.pop();//避免多操作if(node-right)st.push(node-right);//右if(node-left)st.push(node-left);//左st.push(node);//中st.push(NULL);//访问过没做处理使用null来做标记}else{st.pop();//空节点弹出node st.top();//取出栈元素st.pop();result.push_back(node-val);//加入结果集}}return result;}
};
后序遍历使用统一迭代法来实现只是顺序部分调换一下即可实现
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode*st;vectorintresult;if(root ! NULL)st.push(root);//加入根节点//循环条件while(!st.empty()){TreeNode* node st.top();//指针指向根节点//节点不为空就加入遇到空节点加入结果集if(node ! NULL){st.pop();//避免多操作st.push(node);//中st.push(NULL);//访问过没做处理使用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;}
};
5.二叉树层序遍历
二叉树层序遍历102题
题目描述给你一个二叉树请你返回其按 层序遍历 得到的节点值。 即逐层地从左到右访问所有节点。
输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]
队列先进先出符合一层一层遍历的逻辑而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。层序就是图中的广度优先遍历迭代法
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode*que;//定义一个队列去迭代if(root ! NULL)que.push(root);//如果根节点不为0将根节点压入队列vectorvectorintresult;//结果集//循环条件队列不为空while(!que.empty()){int size que.size();//定义队列的大小vectorintvec;//每层数组接收//从队列里遍历元素for(int i 0;i size;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;}
};
递归法
class Solution {
public:void order(TreeNode* cur, vectorvectorint result, int depth){if (cur nullptr) return;if (result.size() depth) result.push_back(vectorint());result[depth].push_back(cur-val);order(cur-left, result, depth 1);order(cur-right, result, depth 1);}vectorvectorint levelOrder(TreeNode* root) {vectorvectorint result;int depth 0;order(root, result, depth);return result;}
};
记住size是不可缺少的因为que.size()在不断地变化
二叉树的层次遍历 II107题
题目描述给定一个二叉树返回其节点值自底向上的层次遍历。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历
输入root [3,9,20,null,null,15,7]
输出[[15,7],[9,20],[3]]
思路类似上提最后反转数组即可
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {queueTreeNode*que;//定义一个队列去迭代if(root ! NULL)que.push(root);//如果根节点不为0将根节点压入队列vectorvectorintresult;//结果集//循环条件队列不为空while(!que.empty()){int size que.size();//定义队列的大小vectorintvec;//每层数组接收//从队列里遍历元素for(int i 0;i size;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;}
};
二叉树的右视图 199题
题目描述给定一棵二叉树想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 思路层序遍历每次取队列尾部的值即可层序遍历每次取最后队列尾部元素即可
class Solution {
public:vectorint rightSideView(TreeNode* root) {queueTreeNode* que;//定义一个队列vectorint result;//结果if(root ! NULL)que.push(root);//根指针不为空//循环条件while (!que.empty()) {int size que.size();//需要预存队列大小//队列里遍历元素for (int i 0; i size; i) {TreeNode* node que.front();//当前指针指向队头元素que.pop();//弹出if(i (size - 1))result.push_back(node-val);//取最后队尾元素放到结果集if(node-left)que.push(node-left);//左孩子if(node-right)que.push(node-right);//右孩子}}return result;}
};
二叉树的层平均值637题
题目描述给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。 思路层序遍历 把一层求个总和在取一个均值
class Solution {
public:vectordouble averageOfLevels(TreeNode* root) {queueTreeNode*que;//定义队列程序遍历vectordoubleresult;//结果注意数据类型if(root ! NULL)que.push(root);//不为空指针while(!que.empty()){int size que.size();//注意预存队列大小double sum 0;//要定义一个和值for(int i 0;i size;i){TreeNode* node que.front();que.pop();sum node-val;//计算每层的和if(node-left)que.push(node-left);if(node-right)que.push(node-right);}result.push_back(sum/size);//我们把均值加入结果集中}return result;}
}; N叉树的层序遍历429题
题目描述给定一个 N 叉树返回其节点值的层序遍历。 (即从左到右逐层遍历)。 思路层序遍历就是孩子多了而已
class Solution {
public:vectorvectorint levelOrder(Node* root) {queueNode*que;vectorvectorintresult;if(root ! NULL)que.push(root);while(!que.empty()){int size que.size();vectorintvec;for(int i 0;i size;i){Node* node que.front();que.pop();vec.push_back(node-val);//遍历多个子孩子节点for(int j 0;j node-children.size();j){if(node-children[j])que.push(node-children[j]);}}result.push_back(vec);}return result;}
}; 在每个树行中找最大值515题
题目描述您需要在二叉树的每一行中找到最大的值。 思路层序遍历找每一行的最大值即可
class Solution {
public:vectorint largestValues(TreeNode* root) {queueTreeNode*que;vectorintresult;if(root ! NULL)que.push(root);while(!que.empty()){int size que.size();int maxvalue INT_MIN;for(int i 0;i size;i){TreeNode* node que.front();que.pop();maxvalue node-val maxvalue ? node-val : maxvalue;//每一行取最大值if(node-left)que.push(node-left);if(node-right)que.push(node-right);}result.push_back(maxvalue);}return result;}
}; 填充每个节点的下一个右侧节点指针116题
题目描述
给定一个完美二叉树其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node {int val;Node *left;Node *right;Node *next;
}填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
初始状态下所有 next 指针都被设置为 NULL。 思路迭代法层序遍历 在单层遍历的时候记录一下本层的头部节点然后在遍历的时候让前一个节点指向本节点就可以了
class Solution {
public:Node* connect(Node* root) {queueNode* que;if (root ! NULL)que.push(root);while (!que.empty()) {int size que.size();Node* nodePre;Node* node;for (int i 0; i size; i) {if (i 0) {nodePre que.front(); // 取出一层的头结点que.pop();node nodePre;} else {node que.front();que.pop();nodePre-next node; // 本层前一个节点next指向本节点nodePre nodePre-next;}if (node-left)que.push(node-left);if (node-right)que.push(node-right);}nodePre-next NULL; // 本层最后一个节点指向NULL}return root;}
}; 填充每个节点的下一个右侧节点指针II117题
题目描述
思路和上面那个一样只不过题目改成了完全二叉树
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* nodepre;for(int i 0;i size;i){if(i 0){nodepre que.front();que.pop();node nodepre;}else{node que.front();que.pop();nodepre-next node;nodepre nodepre-next;}if(node-left)que.push(node-left);if(node-right)que.push(node-right);}nodepre-next NULL;}return root;}
};
6.翻转二叉树226题
思路反转二叉树把每个节点的左右孩子交换一下即可遍历过程中反转每个节点左右孩子就可以实现
递归法实现三部曲确定返回值和参数参数主要是树的根节点指针返回值就是树的节点就好确定终止条件节点为空就返回确定单层递归的逻辑前序遍历先进行交换左右孩子节点然后反转左子树反转右子树
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root NULL)return root;//根节点为空直接返回swap(root-left,root-right);//前序遍历的方法中invertTree(root-left);//左invertTree(root-right);//右return root;//最后返回}
};
迭代法实现将中序遍历迭代法实现即可
class Solution {
public:TreeNode* invertTree(TreeNode* root) {stackTreeNode*st;//申请一个栈if(root NULL)return root;//判断st.push(root);//栈建立联系//循环条件while(!st.empty()){TreeNode* node st.top();//节点是栈顶元素st.pop();//弹出swap(node-left,node-right);//中间处理方式if(node-right)st.push(node-right);//右if(node-left)st.push(node-left);//左}return root;}
};
层序遍历层序遍历也可以把每个节点的左右孩子都翻转一遍
class Solution {
public:TreeNode* invertTree(TreeNode* root) {queueTreeNode* que;//用队列层序遍历if (root NULL)return root;que.push(root);//队列和树联系while (!que.empty()) {int size que.size();//队列大小需要记录//每层去迭代for (int i 0; i size; i) {TreeNode* node que.front();//队头元素是需要处理的节点que.pop();//弹出swap(node-left, node-right);//需要处理的逻辑if(node-left)que.push(node-left);//左if(node-right)que.push(node-right);//右}}return root;}
};
7.对称二叉树101题
题目描述给定一个二叉树检查它是否是镜像对称的。
输入root [1,2,2,3,4,4,3]
输出true
思路我们需要比较根节点的左子树与右子树是不是相互翻转的其实我们要比较的是两个树这两个树是根节点的左右子树比较的是两个子树的里侧和外侧的元素是否相等。遍历只能是“后序遍历”要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等遍历两棵树而且要比较内侧和外侧节点是一个树的遍历顺序是左右中一个树的遍历顺序是右左中。
递归写法确定函数返回值和参数终止条件单层递归逻辑
class Solution {
public://递归三部曲首先确定返回值和参数参数是左右子树bool compare(TreeNode* left,TreeNode* right){if(left NULL right ! NULL)return false;//左节点为空右节点不空else if(left ! NULL right NULL)return false;//左节点不空右节点为空else if(left NULL right NULL)return true;//都为空else if(left-val ! right-val)return false;//都不为空但是数值不等bool outside compare(left-left,right-right);//单层递归逻辑左子树的左节点和右子树的右节点bool inside compare(left-right,right-left);//左子树的右节点和右子树的左节点采用后序遍历bool issame outside inside;//中return issame;}bool isSymmetric(TreeNode* root) {if(root NULL)return false;//不对空指针操作return compare(root-left,root-right);}
};
迭代法队列方法实现
class Solution {
public:bool isSymmetric(TreeNode* root) {queueTreeNode*que;//定义一个队列if(root NULL)return true;//如果为空返回正确que.push(root-left);//我们把根节点的左子树和右子树的根节点加入队列que.push(root-right);//循环条件while(!que.empty()){TreeNode* leftnode que.front();//左节点指针和右节点指针que.pop();TreeNode* rightnode que.front();que.pop();//左右都为空继续上述操作if(!leftnode !rightnode){continue;}//左子树和右子树一个不为空或者节点的值不相等返回错if(!leftnode || !rightnode || leftnode-val ! rightnode-val){return false;}//我们首先先放左节点的左子树再放右节点的右子树que.push(leftnode-left);que.push(rightnode-right);//再左节点的右子树再放右节点的左子树que.push(leftnode-right);que.push(rightnode-left);}return true;}
};
迭代法栈实现也可以
class Solution {
public:bool isSymmetric(TreeNode* root) {stackTreeNode*st;//定义一个栈if(root NULL)return true;//如果为空返回正确st.push(root-left);//我们把根节点的左子树和右子树的根节点加入栈st.push(root-right);//循环条件while(!st.empty()){TreeNode* leftnode st.top();//左节点指针和右节点指针st.pop();TreeNode* rightnode st.top();st.pop();//左右都为空继续上述操作if(!leftnode !rightnode){continue;}//左子树和右子树一个不为空或者节点的值不相等返回错if(!leftnode || !rightnode || leftnode-val ! rightnode-val){return false;}//我们首先先放左节点的左子树再放右节点的右子树st.push(leftnode-left);st.push(rightnode-right);//再左节点的右子树再放右节点的左子树st.push(leftnode-right);st.push(rightnode-left);}return true;}
};
8.二叉树的最大深度104题
题目描述给定一个二叉树找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。 思路前序求得深度后序求得高度根节点的高度就是二叉树的最大深度通过后序求的根节点高度来求的二叉树最大深度。 二叉树节点的深度指从根节点到该节点的最长简单路径边的条数或者节点数取决于深度从0开始还是从1开始二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数或者节点数取决于高度从0开始还是从1开始
递归法使用后序写的代码
class Solution {
public://递归函数返回值和参数深度值和节点int getdepth(TreeNode* node){if(node NULL)return 0;//终止条件int leftdepth getdepth(node-left);//左int rightdepth getdepth(node-right);//右int depth 1 max(leftdepth,rightdepth);//中注意根节点需要加1return depth;}int maxDepth(TreeNode* root) {return getdepth(root);//调用递归函数
};
递归法使用前序遍历回溯
class Solution {
public:int result;//使用前序遍历递归void getdepth(TreeNode* node,int depth){result result depth ? result : depth;//中if(node-left NULL node-right NULL)return;//规定终止条件当前节点左右子树都为空就停止//左if(node-left){depth;getdepth(node-left,depth);depth--;//回溯}//右if(node-right){depth;getdepth(node-right,depth);depth--;//回溯}return ;}int maxDepth(TreeNode* root) {result 0;if(root NULL)return result;getdepth(root,1);return result;}
};
迭代法使用层序遍历实现在二叉树中一层一层的来遍历二叉树记录一下遍历的层数就是二叉树的深度
class Solution {
public:int maxDepth(TreeNode* root) {queueTreeNode*que;//队列层序遍历int result 0;//结果if(root NULL)return 0;que.push(root);while(!que.empty()){int size que.size();result;//记录深度for(int i 0;i size;i){TreeNode* node que.front();que.pop();if(node-left)que.push(node-left);if(node-right)que.push(node-right);}}return result;}
};
n叉树的最大深度 559题
题目描述
给定一个 n 叉树找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 递归法和上述思想类似
class Solution {
public:int maxDepth(Node* root) {if(root NULL)return 0;//终止条件int depth 0;//寻找子树的每一个最大深度for(int i 0;i root-children.size();i){depth max(depth,maxDepth(root-children[i]));}return depth1;}
};
迭代法
class Solution {
public:int maxDepth(Node* root) {queueNode*que;if(root ! NULL)que.push(root);int depth 0;while(!que.empty()){int size que.size();depth;for(int i 0;i size;i){Node* node que.front();que.pop();for(int j 0;j node-children.size();j){if(node-children[j])que.push(node-children[j]);}}} return depth;}
};
9. 二叉树的最小深度111题
题目描述
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。 思路 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。左右孩子都为空的节点才是叶子节点
如果左子树为空右子树不为空说明最小深度是 1 右子树的深度。
反之右子树为空左子树不为空最小深度是 1 左子树的深度。 最后如果左右子树都不为空返回左右子树深度最小值 1 。 递归法后序遍历
class Solution {
public://递归算法使用后序遍历来实现int getdepth(TreeNode* node){if(node NULL)return 0;int leftdepth getdepth(node-left);//左int rightdepth getdepth(node-right);//右//左子树为空右子树不为空不是最小深度if(node-left NULL node-right ! NULL){return 1rightdepth;}//右子树为空左子树不为空不是最小深度if(node-right NULL node-left ! NULL){return 1leftdepth;}//和最大深度处理差不多int depth 1min(leftdepth,rightdepth);return depth;}int minDepth(TreeNode* root) {return getdepth(root);}
};
迭代法层序遍历只有当左右孩子都为空的时候才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点
class Solution {
public:int minDepth(TreeNode* root) {queueTreeNode* que;if (root ! NULL)que.push(root);int depth 0;while (!que.empty()) {int size que.size();depth;for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (node-left)que.push(node-left);if (node-right)que.push(node-right);//注意左右节点都为0就需要退出了if (!node-left !node-right) {return depth;}}}return depth;}
};
总结
二叉树理论基础二叉树的种类满二叉树度为0或2深度为k有2^k-1个节点完全二叉树保证最左边的全是有节点优先级队队列是堆也就是完全二叉树二叉搜素树是一个有序数左子树小于根节点右子树大于根节点左右子树也都是二叉搜索树平衡二叉搜索树左右子树的高度不超过1且也是平衡二叉树mapset底层都是平衡二叉搜索树存储方式链式两个指针一个根节点和顺序数组存储遍历方式深度优先遍历前中后序注意迭代法和递归法的写法广度优先遍历层序遍历前中后指的是中间节点的位置左指的是左子树右指的是右子树深度优先一般使用栈迭代广度优先使用队列去迭代注意二叉树的节点结构
递归遍历三部曲确定返回值和参数类型确定终止条件确定单层递归逻辑注前中后序的递归代码写法
迭代遍历前中后序使用栈去实现前序后序遍历都是先处理元素放入数组在遍历节点访问元素和处理元素顺序一致中间节点中序遍历是左中右的顺序先访问根节点在一层一层向下访问到达最左面叶片节点处理节点中序遍历需要指针遍历来访问节点栈来处理元素前序后序节点改变一下顺序就可以实现中序遍历不可以
二叉树统一迭代方式将访问的节点放入栈中把要处理的节点也放入栈中但是要做标记就是要处理的节点放入栈之后紧接着放入一个空指针作为标记。
二叉树层序遍历使用队列来进行迭代注意代码写法注需要记录队列大小因为大小来回变化在内部用一个for循环遍历元素进行遍历左右子树
翻转二叉树递归法使用前序遍历交换两个子树再进行后面的左子树右子树操作层序遍历也可以实现需要处理的位置
对称二叉树我们需要比较里侧和外侧是否相等只可以后序遍历其实一个树是左右中另一个是右左中递归写法要注意考虑终止条件设定迭代法使用栈和队列都可以实现注意要传左右子树
二叉树的最大深度前序求得深度后序求得高度后序求的根节点高度来求的二叉树最大深度。深度是二叉树根节点到所求节点的距离高度则是叶片节点到根节点注意使用前序需要使用回溯层序也可以实现每遍历一层深度1注n叉树就是子树多了而已其实操作一样
二叉树的最小深度前序求得深度后序求得高度最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。左右孩子都为空的节点才是叶子节点注意节点为空情况的讨论左子树为空右子树不为空说明最小深度是 1 右子树的深度。右子树为空左子树不为空最小深度是 1 左子树的深度。 最后如果左右子树都不为空返回左右子树深度最小值 1 。层序遍历只有当左右孩子都为空的时候才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点。
