【数据结构】二叉树进阶题目练习

news/2024/10/18 14:18:30/

文章目录

    • 二叉树创建字符串
    • 二叉树的分层遍历1
    • 二叉树的分层遍历2
    • 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
    • 二叉树搜索树转换成排序双向链表
    • 二叉树展开为链表
    • 根据一棵树的前序遍历与中序遍历构造二叉树
    • 根据一棵树的中序遍历与后序遍历构造二叉树
    • 二叉树的前序遍历 非递归迭代实现
    • 二叉树中序遍历 非递归迭代实现
    • 二叉树的后序遍历 非递归迭代实现

二叉树创建字符串

给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串,空节点使用一对空括号对 “()” 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对,

https://leetcode-cn.com/problems/construct-string-from-binary-tree/

前序遍历的方式, 先处理根节点:

左树怎么处理? 右树怎么处理? 什么时候需要加括号！

image-20220425102747271

err:

image-20220425102835207

方法1:

class Solution {public:string tree2str(TreeNode* root){string ans;if(root == nullptr){return ans;}ans += to_string(root->val);//有左 || 无左有右  -> 就需要加括号//root->left || root->right就可以代表上面的描述if(root->left || root->right){ans += '(';ans += tree2str(root->left);ans += ')';}//右树只要不为空就加括号,否则不处理右树if(root->right){ans += '(';ans += tree2str(root->right);ans += ')';}return ans;}
};

缺点: 每一次返回都是传值返回, 由于返回的ans是临时变量,不能使用引用返回, 所以是深拷贝

优化:写子函数,传引用作为参数,减少拷贝

class Solution {public:void _tree2str(TreeNode* root,string& ans){if(root == nullptr){return ;}//前序遍历序列化,需要判断是否需要加括号ans += to_string(root->val);//左树是否需要加括号:有左 || 无左有右  -> 就需要加括号if(root->left || root->right){ans += '(';_tree2str(root->left,ans);ans += ')';}//判断右树是否需要加括号->右树不为空,就需要加if(root->right){ans += '(';_tree2str(root->right,ans);ans += ')'; }}string tree2str(TreeNode* root) {string ans;_tree2str(root,ans);return ans;}
};

二叉树的分层遍历1

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

image-20220412224115316d

class Solution {public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;if(root == nullptr){return vv;//返回空容器}queue<TreeNode* >q;//用于层序遍历的容器q.push(root);//先把根节点入队列while(!q.empty()){int size = q.size();//这一层有多少个节点vector<int> v;for(int i =0;i<size;i++){//对这一层的节点做处理TreeNode* node = q.front();q.pop();v.push_back(node->val);//左右孩子不为空,就进队列if(node->left){q.push(node->left);}if(node->right){q.push(node->right);}}//把这一层的结果放到容器中vv.push_back(v);}return vv;}
};

二叉树的分层遍历2

https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

image-20220412224222214

此题和上面的区别就是,这个是自底向上存放结果,而上一题是自顶向下存放结果,

所以我们处理的方法是：先得到自顶向下的结果,然后翻转容器,得到的就是自底向上的结果

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> vv;if(root == nullptr){return vv;//返回空容器}queue<TreeNode* >q;//用于层序遍历的容器q.push(root);//先把根节点入队列while(!q.empty()){int size = q.size();//这一层有多少个节点vector<int> v;for(int i =0;i<size;i++){//对这一层的节点做处理TreeNode* node = q.front();q.pop();v.push_back(node->val);//左右孩子不为空,就进队列if(node->left){q.push(node->left);}if(node->right){q.push(node->right);}}//把这一层的结果放到容器中vv.push_back(v);}reverse(vv.begin(),vv.end());return vv;}
};

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

什么叫公共祖先: 沿着自己的路径往上走,最坏就走到根节点, 二者的交点就是祖先

情况分析:该类题目的常见类型:

1.如果是三叉链

即左右孩子指针 + 父亲节点指针

此时可以转化为链表相交问题:

  • 两个节点不断往上走到根节点位置,统计二者的长度,然后长链表先走差距步,然后二者再一起走,当二者相遇就是祖先

image-20220425104508101

2.如果是搜索树:

a.如果一个值比当前root节点的值小,一个值比当前root节点的值大 ->我就是最近公共祖先

b.如果两个值都比当前root节点的值小 -> 去左树递归查找

c.如果两个值都比当前root节点的值大-> 去右树递归查找

3.普通的二叉树

相比搜索二叉树,此时不能使用值的大小去判断在左树还是右树！此时要整棵树查找

image-20220425104545500

image-20220424204702774

此时是第三种 普通二叉树的情况:

方法1:

设计一个子函数Find:用于查找x这个节点在不在

对要查找的两个节点的情况分析:

如果其中一个节点是当前根节点,最近公共祖先就是当前节点

如果两个节点不在root这棵树的同一侧:当前root节点就是二者的最近公共祖先

如果两个节点都在root的右树:去root的右树寻找

如果两个节点都在root的左数:去root的左树查找

为了方便,可以设计4个变量分别标志p和q是否在左树/右树

子函数Find:

//查找x这个节点是否在这棵树
bool Find(TreeNode* root,TreeNode* x)
{//root为空树if(root == nullptr) return false;//root就是x节点if(root == x) return true;//去左树和右树查找//任意一棵树找到就说明x在这棵树,所以用的是||的逻辑return Find(root->left,x) || Find(root->right,x);
}

主函数:

注意返回值的问题:

image-20220424211203226

时间复杂度:O(N^2)

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
{//root为空树if(root == nullptr) return nullptr;//如果其中一个节点是当前根节点,最近公共祖先就是当前节点if(root == p || root == q){return root;}//定义4个变量标志p和q在root的哪一侧bool pInLeft,pInRight,qInLeft,qInRight;//如果p/q在左树了就不可能在右树pInLeft = Find(root->left,p);//调用子函数查找p是否在root的左树pInRight = !pInLeft;qInLeft = Find(root->left,q);//调用子函数查找q是否在root的左树qInRight = !qInLeft;//对p和q的情况分析//1.两个节点不在同一侧:根节点就是祖先if((pInLeft&&qInRight) || (pInRight&&qInLeft)){return root;}//2.两个节点都在左树->去左树找else if(pInLeft&&qInLeft){return lowestCommonAncestor(root->left,p,q);}//3.两个节点都在右树->去右树找else if(pInRight&&qInRight){return lowestCommonAncestor(root->right,p,q);}else    //因为p和q都存在,所以不可能走到这里的else{//如果此处不返回,就会报错:不是所有路径都有返回值！//这是语法要求的return nullptr;}
}

方法2:分别求出从根节点到p和q的路径,再找两个路径的交点

这里可以选择把路径加入到栈中,注意栈中最好存放节点指针,如果存的是节点的值,如果存在树中存在相同的值,就会出错(虽然这题说了节点的值不重复)

FindPath函数:把从根节点到x的路径加入到容器中,

注意:要排除节点->回溯 时间复杂度:O(N)

子函数FindPath:查找x节点,并保存沿途的路径节点 返回值为bool类型,用于标志是否发现节点x

不管三七二十一,先把当前节点放到路径容器中

0.如果当前节点为空 ->返回false

1.如果当前节点就是x ->返回true
否则:
2.去左树查找,找到了就返回true,否则就是false
3.去右树查找,找到了就返回true,否则就是false
4.如果走到这一步,说明在当前节点的这颗子树不可能找到x节点,(说明该节点不是从根节点到x节点的路径中的一个节点) 把这个节点从就容器中去掉,然后返回true

image-20220425110858803

// 返回bool类型是为了判断是否发现x,发现了就不需要往下找了
//因为要修改path容器的内容,所以要传引用
bool FindPath(TreeNode* root,TreeNode* x,stack<TreeNode*>& path)
{//当前节点为空 ->返回falseif(root == nullptr) return false;path.push(root);//先把当前节点放到路径中//当前节点就是x节点->返回trueif(root == x) return true;//如果root不是x -> 去当前节点的左树和右树找x,并保存沿途的路径if(FindPath(root->left,x,path)){//在当前节点的左树中找到x了,返回truereturn true;}if(FindPath(root->right,x,path)){//在当前节点的右树找到x,返回truereturn true;}//走到这里,说明当前节点的左树和右树都没有找到x节点->把当前节点在路径中去掉,返回falsepath.pop();return false;
}

主函数:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
{stack<TreeNode*> pPath,qPath;//分别保存到p和q的路径FindPath(root,p,pPath);//得到到p节点的路径,保存到pPathFindPath(root,q,qPath);//得到到q节点的路径,保存到qPath//长的路径容器先走差距步while(qPath.size() != pPath.size()){if(qPath.size() > pPath.size()){qPath.pop();}else{pPath.pop();}}//此时二者得路径长度相同,一起出数据//当二者栈顶元素相同,就是祖先while(qPath.top() != pPath.top()){qPath.pop();pPath.pop();}return qPath.top();
}

方法3:套路

class Solution {
public:struct Info{bool isFindQ;//是否发现qbool isFindP;//是否发现pTreeNode* ans;//记录q和p的公共祖先答案Info(bool isQ, bool isP,TreeNode* an){isFindP = isP;isFindQ = isQ;ans = an;}};Info process(TreeNode* x,TreeNode* p,TreeNode* q){if(x == nullptr){return Info(false,false,nullptr);//设置空信息}Info leftInfo = process(x->left,p,q);Info rightInfo = process(x->right,p,q);//处理x这棵树的信息bool isFindQ = leftInfo.isFindQ || rightInfo.isFindQ || x == q;bool isFindP = leftInfo.isFindP || rightInfo.isFindP || x == p;TreeNode* ans = nullptr;//是否在左树/右树发现答案if(leftInfo.ans != nullptr){ans = leftInfo.ans; }else if(rightInfo.ans != nullptr){ans = rightInfo.ans;}else{//此时走到这,说明没有找到答案//如果在x这棵树即发现了p也发现了q,说明x这个节点就是答案if(isFindP&&isFindQ){ans = x;}}//返回这棵树的信息return Info(isFindQ,isFindP,ans);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return process(root,p,q).ans;}
};

二叉树搜索树转换成排序双向链表

image-20220428210615143

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

方法1:容器作弊法 走一遍中序遍历,把节点的指针放到容器中,然后遍历链接前后两个节点

特殊点:第一个节点的left链接空 最后一个节点的right链接空

class Solution {
public:vector<TreeNode*> v;//存放节点指针//中序遍历void _inOrder(TreeNode* root){if(root == nullptr) return ;_inOrder(root->left);v.push_back(root);_inOrder(root->right);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr) return nullptr;_inOrder(pRootOfTree);//先走一边中序遍历//二叉树的左孩子指针 -> prev  右孩子指针 -> next//第一个节点的prev置为空TreeNode* head = v[0];TreeNode* cur = head;cur->left = nullptr;TreeNode* next = nullptr;for(int i = 0;i<v.size()-1;i++){cur = v[i];next = v[i+1];//cur next前后链接cur ->right = next;next -> left = cur;}//最后一个节点的next置为空v[v.size()-1] -> right = nullptr;return head;}
};

方法2:递归走中序遍历

思想:让每个节点的left指向上一个遍历的节点,让每个节点的right指向下一个遍历的节点

定义两个指针:一个prev 一个 cur,其中cur记录当前中序遍历时到达的节点,prev记录上一次中序遍历时到达的节点

当我们遍历到cur的时候,我们不知道下一个节点是谁,但是我们可以明确知道,prev的下一个节点是cur,cur的上一个节点是prev 即我们可以知道: 此时left是指向前一个指针,right是指向下一个的指针

cur->left = prev
prev->right = cur

注意:由于prev要记录上一次中序遍历的节点,即prev只能存在一个,并非每个栈帧都有一个prev,所以传参的时候,prev要传引用 第一次的时候,prev是nullptr

image-20220428214948944

class Solution {
public://prev传的时引用！！！void InOrderConvert(TreeNode* cur ,TreeNode*& prev){if(cur == nullptr) return ;//中序遍历InOrderConvert(cur->left,prev);//cur和prev链接cur->left = prev;//注意第一次的时候prev时空,所以要判断一下if(prev != nullptr){prev ->right = cur;}prev = cur;//此时的cur就成了上一次中序遍历的节点InOrderConvert(cur->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree){if(pRootOfTree == nullptr){return nullptr;}TreeNode* prev = nullptr;//prev初始化为空InOrderConvert(pRootOfTree,prev);//调用子函数进行处理//先找到原来根节点的位置,然后往前找,找到链表的头TreeNode* head = pRootOfTree;while(head->left){head = head->left;}return head;}
};

二叉树展开为链表

给你二叉树的根结点 root ,请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

方法1:因为展开后的单链表应该与二叉树 先序遍历 顺序相同,所以可以先走一遍前序遍历,把节点存到容器中,然后进行链接

  • 注意:left指针要置空,前一个节点的right指针链接下一个节点
  • 注意:最后一个节点的left和right指针都置为空
class Solution {
public:vector<TreeNode*> v;void preOrder(TreeNode* root){if(root == nullptr ) return ;v.push_back(root);preOrder(root->left);preOrder(root->right);}void flatten(TreeNode* root) {if(root == nullptr) return ;preOrder(root);//遍历容器进行链接for(int i =0;i<v.size()-1;i++ ){v[i]->right = v[i+1];v[i]->left = nullptr;}v[v.size()-1]->right = nullptr;v[v.size()-1]->left = nullptr;}
};

方法2:递归

为了将两个树节点进行链接操作,通常希望它们是前驱和后继的关系

image-20220430105242969

image-20220430110230690

class Solution {
public:TreeNode* pre = nullptr;//记录前一个节点void flatten(TreeNode* root){if (root && (root->left || root->right)) {//先右后左的后序遍历flatten(root->right);flatten(root->left);//进行链接root->right = pre;//将前驱结点作为当前结点的右孩子root->left = nullptr;//当前结点的左孩子置空pre = root; //更新前驱结点}}
};

根据一棵树的前序遍历与中序遍历构造二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

image-20220412230749394

方法1:根据每一棵子树的元素个数划分左树和右树

class Solution {
public://闭区间TreeNode* _buildTree(vector<int> preorder,int preStart,int preEnd,vector<int> order,int orStart,int orEnd){//如果某一个区间不符合,直接返回空if(preStart>preEnd || orStart > orEnd){return nullptr;}//根节点的位置就是前序数组区间的的第一个位置TreeNode* head = new TreeNode(preorder[preStart]);//在中序数组中找到根节点的位置for(int i = orStart;i<=orEnd;i++){if(order[i] == head->val){//构建左树和右树//中序数组中,此时i位置就是根节点在中序数组的位置:左树范围:[orStart,i-1] 根节点：i  右树范围:[i+1,orEnd]//根据左子树个数一样的原则,可以得知,前序遍历中,根节点位置为preStart位置,所以左树的范围是[preStart+1,x]  x-(preStart+1)+1 = i-1-orStart+1  -> x = preStart+i-orStarthead->left = _buildTree(preorder,preStart+1,preStart+i-orStart,order,orStart,i-1);head->right =_buildTree(preorder,preStart+i-orStart+1,preEnd,order,i+1,orEnd);break;}}return head;//最后返回头节点}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {//如果其中一个数组为空 || 两个数组的元素个数不同if(preorder.size() != inorder.size() || preorder.empty() || inorder.empty()){return nullptr;}return _buildTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);}
};

方法2:前序确定根,中序区间分割左右子树

image-20220428215605854

定义一个变量prei标志当前前序数组的位置,确定根位置,然后prei++指向前序数组中下一个根节点的位置,为下一棵子树做准备,然后划分当前节点的左右子树

由于prei的位置是每一层都使用同一个变量往下递归,即函数栈帧中只存在一个prei,所以要传引用

class Solution {
public://前序确定根,中序区间分割左右子树//传5个参数：前序和中序数组 前序中的根位置 中序区间的首尾(闭区间)//注意：prei要传引用,因为每一层递归的prei都是对同一个prei进行修改TreeNode* _buildTree(vector<int>& preorder,vector<int>& inorder,int& prei,int inbegin,int inend){if(inbegin>inend){return nullptr;//区间不存在,返回空树 }TreeNode* root = new TreeNode(preorder[prei]);//前序确定根//在中序数组中找到根位置,划分左右区间int rooti = inbegin;while(rooti<=inend){if(inorder[rooti] == root->val){break;}else{rooti++;}}++prei;//指向前序数组中下一个根节点的位置,为下一棵子树做准备//划分当前节点的左右子树//[inbegin,rooti-1] rooti [rooti+1,inend]root->left = _buildTree(preorder,inorder,prei,inbegin,rooti-1);root->right = _buildTree(preorder,inorder,prei,rooti+1,inend);//返回根位置return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size() != inorder.size() || preorder.empty()  ||inorder.empty()){return nullptr;}int prei = 0;return _buildTree(preorder,inorder,prei,0,inorder.size()-1);}
};

根据一棵树的中序遍历与后序遍历构造二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

和上面前序和中序构建树的方法基本一致！

image-20220429082315692

前序和中序: 前序确定根,中序分割左右区间, 由于前序的访问顺序是:根左右,所以根在前面的位置,所以prei从前序数组的第一个元素0下标位置开始往后走确定每棵子树的根

  • 构造树的时候,先构建左树再构造右树

中序和后序: 后序确定根,中序分割左右区间, 由于后序的访问顺序是:左右根,所以根在后面的位置,所以posi从后序数组最后一个元素posorder.size()-1位置开始往前走确定每棵子树的根

  • 构造树的时候,先构建右树再构造左树

相同点:

由于prei/posi的位置是每一层都使用同一个变量往下递归,即函数栈帧中只存在一个prei/posi,所以要传引用

class Solution {
public:TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,int& posi,int inbegin,int inend){if(inbegin>inend){return nullptr;//区间不存在,返回空树}TreeNode* root = new TreeNode(postorder[posi]);//后序确定根位置//在中序中找到根节点位置int rooti = inbegin;while(rooti<= inend){if(inorder[rooti] == root->val){break;}else{rooti++;}}--posi;//指向后序数组中前一个根节点的位置,为下一棵子树做准备//划分当前节点的左右子树//[inbegin,rooti-1] rooti [rooti+1,inend]//注意:要先构建右树！！再构建左树root->right = _buildTree(inorder,postorder,posi,rooti+1,inend);root->left = _buildTree(inorder,postorder,posi,inbegin,rooti-1);//返回头节点位置return root;} TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size() != postorder.size() ||inorder.empty() || postorder.empty()){return nullptr;}int posi = postorder.size()-1;//根在后面 return _buildTree(inorder,postorder,posi,0,inorder.size()-1);}
};

二叉树的前序遍历 非递归迭代实现

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

class Solution {
public://子函数处理,只有容器要传引用,因为要对容器的内容做修改void _preorderTraversal(TreeNode* root,vector<int>& v){if(root == nullptr){return ;}v.push_back(root->val);//把根节点放到容器中_preorderTraversal(root->left,v);//递归处理左树_preorderTraversal(root->right,v);//递归处理右树}vector<int> preorderTraversal(TreeNode* root) {vector<int> v;_preorderTraversal(root,v);return v;}
};

**方法2:**访问顺序:根 左 右

一棵树的访问分为:

  • 1.访问左路节点,并且左路节点进栈
  • 2.出栈顶元素,去它的右子树, 转化为子问题
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> v;if(root == nullptr) return v;stack<TreeNode*> st;TreeNode* cur = root;//循环结束条件:cur为空&&栈为空,说明所有节点都处理完了while(cur !=nullptr || !st.empty()){//循环每走一次迭代,都表示在访问一棵子树的开始//1.访问左路节点,左路节点进栈while(cur){v.push_back(cur->val);st.push(cur);cur = cur->left;}//2.栈里面左路节点的右子树没有访问,去右树访问TreeNode* top = st.top();st.pop();//3.以子树的方式访问当前栈顶节点右子树cur = top->right;}return v;}
};

二叉树中序遍历 非递归迭代实现

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

class Solution {
public://子函数处理,只有容器要传引用,因为要对容器的内容做修改void _inorderTraversal(TreeNode* root,vector<int>& v){if(root == nullptr){return ;}_inorderTraversal(root->left,v);//递归处理左树v.push_back(root->val);//把根节点放到容器中_inorderTraversal(root->right,v);//递归处理右树}vector<int> inorderTraversal(TreeNode* root){vector<int> v;_inorderTraversal(root,v);return v;}
};

方法2:访问顺序:左 根 右

什么时候能访问当前节点?

先把cur的所有左子树进栈,当我们把节点从栈里面取出来,然后就可以访问当前栈顶节点,然后再去它的右子树

右子树也是一样的递归子问题！

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> v;if(root == nullptr) return v;stack<TreeNode*> st;TreeNode* cur = root;//循环结束条件:cur为空&&栈为空,说明所有节点都处理完了while(cur !=nullptr || !st.empty()){//1.先把左路节点全部进栈while(cur){st.push(cur);cur = cur->left;}//2.访问当前栈顶节点,然后再去访问它的右子树TreeNode* top = st.top();v.push_back(top->val);st.pop();//3.以子树的方式访问当前栈顶节点右子树cur = top->right;}return v;}
};

二叉树的后序遍历 非递归迭代实现

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

class Solution {
public://子函数处理,只有容器要传引用,因为要对容器的内容做修改void _postorderTraversal(TreeNode* root,vector<int>& v){if(root == nullptr){return ;}_postorderTraversal(root->left,v);//递归处理左树_postorderTraversal(root->right,v);//递归处理右树v.push_back(root->val);//把根节点放到容器中}vector<int> postorderTraversal(TreeNode* root){vector<int> v;_postorderTraversal(root,v);return v;}
};

方法2:访问顺序:左 右 根

什么时候能访问当前节点?

当前节点的右树已经访问过了,就可以访问当前节点

  • prev:表示上一个访问的节点, 每访问一个节点,就把当前节点给prev

注意:如果我的右树已经访问过了,那上一个访问的节点一定是我自己右树的根节点

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> v;if(root == nullptr) return v;stack<TreeNode*> st;TreeNode* cur = root;TreeNode* prev = nullptr;//循环结束条件:cur为空&&栈为空,说明所有节点都处理完了while(cur !=nullptr || !st.empty()){//1.先把左路节点全部进栈while(cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();//如果top的右子树已经访问过了,就可以访问top//ps:如果我的右子树为空,或者上一轮访问的节点就是我的右孩子节点,//就说明我的右子树已经访问过了,现在可以访问我//否则就以子树的方式访问当前栈顶节点右子树if(top->right == nullptr || top->right == prev){v.push_back(top->val);prev = top;//更新上一个访问的节点st.pop();}else{cur = top->right;}}return v;}
};

总结:

前序的顺序是:根 左 右

所以我们在把所有左路节点进栈的时候,就可以直接访问当前节点**(把当前节点保存容器中)**

当我们把当前节点的所有左路节点都进栈之后,弹出当前栈顶节点,去当前栈顶节点的右子树以相同的子问题方式进行处理

中序的顺序是: 左 根 右

  • 先把当前节点的所有左路节点进栈
  • 访问当前栈顶节点 (把当前节点保存容器中)
  • 去当前栈顶节点的右子树以子问题的方式进行处理

后序的顺序是: 左 右 根

  • 先把当前节点的所有左路节点进栈

  • 如果当前栈顶节点的右子树已经访问过了 或者当前节点的右子树为空 ,我们才可以访问当前栈顶节点

    • 如果判断是否访问过呢?

      • 我们定义了一个变量prev标志了上一次访问的节点,如果当前节点的右孩子就是prev,说明右子树已经访问过了,

    • 否则:去当前栈顶节点的右子树以子问题的方式进行处理


http://www.ppmy.cn/news/71902.html

相关文章

Hadoop学习全程记录——hive入门

Hadoop学习全程记录——hive入门

hive是Facebook的产品&#xff0c;很不错。 官方文档&#xff1a;http://wiki.apache.org/hadoop/Hive/GettingStarted有很详细说明。 基本上根据文档能对hive快速入门。在使用过程中可能会出现以下问题&#xff1a; 当执行下面命令时&#xff1a; Java代码 $ $HIVE_HOME/bin…
阅读更多...
虚拟机虚拟环境中安装dirmap并更改Bin目录

虚拟机虚拟环境中安装dirmap并更改Bin目录

在 Red Hat Enterprise Linux 8 中安装 dirmap 可以按照以下步骤进行&#xff1a; 激活虚拟环境&#xff1a;打开终端或命令提示符&#xff0c;并导航到虚拟机的工作目录。输入命令来激活虚拟环境。具体的命令取决于您使用的虚拟环境管理工具&#xff0c;例如 virtualenv 或 c…
阅读更多...
香农信息论的基本理论探究

香农信息论的基本理论探究

摘要&#xff1a;信息是自从人类出现以来就存在于这个世界上了&#xff0c;天地万物&#xff0c;飞禽走兽&#xff0c;以及人类的生存方式都离不开信息的产生和传播。人类每时每刻都在不停的接受信息&#xff0c;传播信息&#xff0c;以及利用信息。从原来的西汉时期的造纸&…
阅读更多...
云厂商纷纷降价开启新一轮价格大战，行业竞争加剧未来何从？

云厂商纷纷降价开启新一轮价格大战，行业竞争加剧未来何从？

5月16日晚间&#xff0c;腾讯云和移动云两大云服务商相继宣布对旗下多款核心产品进行降价。其中&#xff0c;腾讯云降价幅度最高达40%&#xff0c;移动云部分产品直降60%。 而就在20天前4月26日阿里云2023合作伙伴大会上&#xff0c;阿里巴巴CEO张勇率先宣布启动“史上最大规模…
阅读更多...
基于SpringBoot的人事管理系统的设计与实现

基于SpringBoot的人事管理系统的设计与实现

背景 人事管理管理方面的任务繁琐,以至于公司每年都在人事管理这方面投入较多的精力却效果甚微,人事管理系统的目标就是为了能够缓解人事管理工作方面面临的压力,让人事管理方面的工作变得更加高效准确。 系统架构 考虑到实际生活中在人事管理方面的需要以及对该系统认真的分…
阅读更多...
MNN-YOLOv8 c++ 推理+交叉编译

MNN-YOLOv8 c++ 推理+交叉编译

使用 https://github.com/wangzhaode/yolov8-mnn.git 进行图片检测推理 1,下载MNN 2,ubuntu编译MNN cd MNN\ mkdir build && cd build && cmake .. -DMNN_BUILD_OPENCV=ON -DMNN_IMGCODECS=ON && make -j8 3,新建CLion共享动态库工程 新建src,includ…
阅读更多...
RK系列（RK3568）SATA MSATA调试和无法识别问题

RK系列（RK3568）SATA MSATA调试和无法识别问题

SOC：RK3568 Linux：kernel-4.19 Android：12 芯片资源介绍 RK3568 资源 速率 支持 PM 芯片扩展 PHY 复用 SATA0
阅读更多...
LSTM-理解 Part-2（RNN的局限性）

LSTM-理解 Part-2（RNN的局限性）

之前写过一部分LSTM-理解 Part-1&#xff08;RNN&#xff1a;循环神经网络&#xff09; 这是其中的第二部分&#xff0c;阐述RNN的局限性。 The Problem of Long-Term Dependencies 长期依赖问题 长期依赖问题指的是在序列数据中&#xff0c;某些元素之间存在着较长时间的依赖…
阅读更多...
最新文章

Copyright @ 2022~2023