数据结构 之 树习题 力扣oj(附加思路版)

层序遍历

算法流程:

        1．创建一个队列记为que,将根节点放入队列。

        2.每次从队列中弹出一个节点，记为node。

        3.第三步看这个node有没有左孩子，如果有左孩子把左孩子放入到队列中，如果node有右孩子，把右孩子放入到队列中。

        4．重复步骤二和步骤三，直到队列为空。

相关函数和知识： 

#include"Tree.h"
int main()
{vector<int>vec;//二维数组就是一维数组中的元素是一维数组vector<vector<int>>vec1;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:vector<vector<int>> levelOrder(TreeNode* root) {if(root==nullptr) return {};queue<TreeNode*>que;que.push(root);vector<vector<int>>res;while(!que.empty()){vector<int>vec;int n=que.size();for(int i=0;i<n;i++){ TreeNode*front=que.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:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if(root==nullptr) return {};vector<vector<int>>res;queue<TreeNode*>que;que.push(root);bool flag=false;while(!que.empty()){vector<int>vec;//写在循环里会每次都清空int n=que.size();for(int i=0;i<n;i++){TreeNode*front=que.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(root==nullptr) return ;stack<TreeNode*>stk;stk.push(root);TreeNode *H=new TreeNode(),*T=H;//因为头节点不知道拼在哪 故创建一个虚头节点while (!stk.empty()){TreeNode* top = stk.top();stk.pop();T->right=top;T->left=nullptr;T=T->right;if (top->right) stk.push(top->right);//因为栈是后进先出 所以右子树先进if (top->left) stk.push(top->left);}delete H;}
};