jsp网站开发实训,wordpress超详细教程视频教程,音乐网站要怎么做,网站建设相关业务层序遍历 算法流程: 1#xff0e;创建一个队列记为que,将根节点放入队列。 2.每次从队列中弹出一个节点#xff0c;记为node。 3.第三步看这个node有没有左孩子#xff0c;如果有左孩子把左孩子放入到队列中#xff0c;如果node有右孩子#xff0c;把右孩子放入到队列中。…层序遍历 算法流程: 1创建一个队列记为que,将根节点放入队列。 2.每次从队列中弹出一个节点记为node。 3.第三步看这个node有没有左孩子如果有左孩子把左孩子放入到队列中如果node有右孩子把右孩子放入到队列中。 4重复步骤二和步骤三直到队列为空。 相关函数和知识
#includeTree.h
int main()
{vectorintvec;//二维数组就是一维数组中的元素是一维数组vectorvectorintvec1;vec1.push_back(vec);//排序函数sort(vec.begin(), vec.end());//从小到大排序sort(vec.rbegin(), vec.rend());//从大到小排序reverse(vec.begin(), vec.end());//反转数组
}二叉树的层序遍历
102. 二叉树的层序遍历https://leetcode.cn/problems/binary-tree-level-order-traversal/
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 思路 通过维护一个队列实现了对二叉树的层序遍历。首先根节点入队。然后当队列不为空时循环执行遍历当前队列中的所有节点将它们的值收集到一个二维向量中并将它们的非空左右子节点依次入队。每完成一层的遍历就将这一层的向量添加到结果向量中直到遍历完所有层。 class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {if(rootnullptr) return {};queueTreeNode*que;que.push(root);vectorvectorintres;while(!que.empty()){vectorintvec;int nque.size();for(int i0;in;i){ TreeNode*frontque.front();que.pop();vec.push_back(front-val);if(front-left)que.push(front-left);if(front-right)que.push(front-right);}res.push_back(vec);}return res;}
}; 二叉树的锯齿形层序遍历
103. 二叉树的锯齿形层序遍历https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/ 给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。 思路 这段代码实现了二叉树的锯齿形层序遍历。它使用了队列来进行层序遍历同时通过一个布尔变量 flag 来标记是否需要反转当前层的节点值顺序。每次遍历一层时先将该层的节点值存入一个临时的 vector 中然后根据 flag 变量的值决定是否需要反转该 vector最后将其加入结果 vector 中。这样可以实现从左向右和从右向左交替进行层序遍历。 class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root) {if(rootnullptr) return {};vectorvectorintres;queueTreeNode*que;que.push(root);bool flagfalse;while(!que.empty()){vectorintvec;//写在循环里会每次都清空int nque.size();for(int i0;in;i){TreeNode*frontque.front();que.pop();vec.push_back(front-val);if(front-left) que.push(front-left);if(front-right) que.push(front-right);}if (flag) reverse(vec.begin(), vec.end());flag!flag;res.push_back(vec);}return res;}
}; 先序遍历 Preorder算法流程: 1先申请一个栈记为stk。 2然后将根节点压入stk 中。 3.每次从stk 中弹出栈顶节点记为cur然后打印cur的值。如果cur的右子节点不为空将cur的右子树压入stk 中。如果cur的左子树不为空将cur的左子节点压入stk 中。不断重复次步骤3直到stk为空循环结束。 二叉树展开为链表
114. 二叉树展开为链表https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
提示
给你二叉树的根结点 root 请你将它展开为一个单链表
展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。 思路 通过先序遍历二叉树的方式将每个节点按顺序连接到单链表中。利用栈来模拟递归的过程先将根节点入栈然后不断弹出栈顶节点将其右子节点和左子节点依次入栈同时将当前节点连接到链表中。 class Solution {
public:void flatten(TreeNode* root) {if(rootnullptr) return ;stackTreeNode*stk;stk.push(root);TreeNode *Hnew TreeNode(),*TH;//因为头节点不知道拼在哪 故创建一个虚头节点while (!stk.empty()){TreeNode* top stk.top();stk.pop();T-righttop;T-leftnullptr;TT-right;if (top-right) stk.push(top-right);//因为栈是后进先出 所以右子树先进if (top-left) stk.push(top-left);}delete H;}
};
