[广度优先搜索]二叉树的层序遍历

编程入门行业动态更新时间:2024-10-24 08:22:31

[广度优先搜索]二叉树的层序<a href=https://www.elefans.com/category/jswz/34/1771029.html style= 遍历"/>

[广度优先搜索]二叉树的层序遍历

前提：

题目：

1.二叉树的层序遍历

思路：

代码：

2.二叉树的层序遍历

思路：

链接：

3.二叉树的层序遍历

思路：

链接:

代码：

4.填充每个节点的下一个右侧节点指针

链接：

思路：

5.填充每个节点的下一个右侧节点指针 II

链接:

思路：

6.二叉树的锯齿形层序遍历

链接：

题目：

思路：

7.N 叉树的层序遍历

思路：

前提：

首先我们要达成一个共识，进行二叉树的层序遍历的方法叫做广度优先搜索，是使用了队列这个数据结构来实现的

题目：

1.二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。（即逐层地，从左到右访问所有节点）。

层序遍历结果为 3 9 20 15 7

思路：

我们先将根节点入队，

如果队列不为空，取队首元素，如果该元素左子树不为空，入队，如果该元素右子树不为空，入队；

直至队列位空，层序遍历完毕；

代码：
vector<int> levelOrder(TreeNode* root) {vector<int> ret;if(root==nullptr)return ret;
//根节点不为空，先将根节点入队TreeNode* curnode=root;queue<TreeNode*> que;que.push(curnode);TreeNode* end=root;while(!que.empty()){TreeNode* top=que.front();que.pop();
//队首元素左子节点存在，入队if(top->left!=nullptr)que.push(top->left);
//队首元素右子节点存在，入队if(top->right!=nullptr)que.push(top->right);ret.push_back(top->val);}
//队列为空，层序遍历完毕return ret;}

2.二叉树的层序遍历

思路：

相较于1而言，只是将每层的数放在一个数组内，将整个树的结果存放在二位数组内，因此我们只要知道每一层的节点个数，就能够完成上面的层序遍历

（1.采用计数的方法，记录每一层的节点个数，如果全部遍历完毕，将一维数组的结果放入二位数组中

vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;if(root==nullptr){return result;}
//nodeCount正在遍历的层的节点数int nodeCount=1;queue<TreeNode*> que;que.push(root);
//curlevelCount下一层的节点个数int curlevelCount=0;vector<int> arr;while(!que.empty()){TreeNode* tmp=que.front();que.pop();
//每遍历一个节点，本层节点个数减1，本层节点个数为0的时候，本层节点全部遍历完毕；nodeCount--;arr.push_back(tmp->val);if(tmp->left!=nullptr){que.push(tmp->left);curlevelCount++;}if(tmp->right!=nullptr){que.push(tmp->right);curlevelCount++;}if(nodeCount==0){result.push_back(arr);arr.clear();nodeCount=curlevelCount;curlevelCount=0;}}return result; }

(2.记录每层最后一个节点，当我们正在遍历的节点是本层的最后一个节点，那么我们就可以将以为数组的结果，放入二位数组中

vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>>ret;if(root==nullptr)return ret;queue<TreeNode*> que;que.push(root);
//end本层的最后一个节点TreeNode* end=root;
//nextend下一层的最后一个节点TreeNode* nextend=root;vector<int> arr;while(!que.empty()){TreeNode* Node=que.front();arr.push_back(Node->val);que.pop();if(Node->left!=nullptr){que.push(Node->left);//防止出现子节点为空的情况nextend=Node->left;}if(Node->right!=nullptr){que.push(Node->right);//防止出现子节点为空的情况nextend=Node->right;}if(Node==end){   end=nextend;ret.push_back(arr);arr.clear();}}return ret;}

优化：当我们取到最后一个节点的时候，下一层的最后一个节点就是队列当中的末尾元素

 vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ret;if(root==nullptr)return ret;TreeNode* curnode=root;queue<TreeNode*> que;que.push(curnode);TreeNode* end=root;vector<int> arr;while(!que.empty()){TreeNode* top=que.front();que.pop();if(top->left!=nullptr)que.push(top->left);if(top->right!=nullptr)que.push(top->right);arr.push_back(top->val);if(top==end){//优化的地方ret.push_back(arr);arr.clear();end=que.back();}}return ret;}

链接：

3.二叉树的层序遍历

思路：

我们仅仅只需要将2的二维数组的结果进行逆置，就可以完成3；

链接:

代码：

vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> ret;if(root==nullptr)return ret;TreeNode* curnode=root;queue<TreeNode*> que;que.push(curnode);TreeNode* end=root;vector<int> arr;while(!que.empty()){TreeNode* top=que.front();que.pop();if(top->left!=nullptr)que.push(top->left);if(top->right!=nullptr)que.push(top->right);arr.push_back(top->val);if(top==end){ret.push_back(arr);arr.clear();end=que.back();}}
//逆置题2的结果reverse(ret.begin(),ret.end());return ret;}

4.填充每个节点的下一个右侧节点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

链接：

思路：

(1.采用层序遍历，非本层末尾元素的next指针指向队首元素；本层末尾元素的next指针指向NULL；
 Node* connect(Node* root) {if(root==nullptr){return root;}queue<Node*> que;que.push(root);Node* end=root;while(!que.empty()){Node* tmp=que.front();que.pop();if(tmp->left!=nullptr)que.push(tmp->left);if(tmp->right!=nullptr)que.push(tmp->right);if(tmp==end){end=que.back();tmp->next==nullptr;}else{tmp->next=que.front();}  }return root;}
5.填充每个节点的下一个右侧节点指针 II

链接:

/

思路：

其实本题是可以仿照上一道题的解题思路来进行解决的，其实本题的简单解法就是进行一次层序遍历，将一层的节点全部链接起来。
 Node* connect(Node* root) {if(root==nullptr){//如果这颗树是一颗空树，直接返回空指针就可以了return root;}queue<Node*> que;que.push(root);Node* end=root;while(!que.empty()){Node* tmp=que.front();que.pop();if(tmp==end){//如果当前的节点是本层的最后一个节点，next指针域指向nullptrtmp->next==nullptr;}else{//如果当前的节点不是本层的最后一个节点的话，next指针域指向本层的下一个节点， //其实该节点也就是队列中的首个节点tmp->next=que.front();}if(tmp->left!=nullptr){que.push(tmp->left);}if(tmp->right!=nullptr){que.push(tmp->right);}if(tmp==end){end=que.back();}}return root;}

6.二叉树的锯齿形层序遍历

链接：

/

题目：

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下：

[
[3],
[20,9],
[15,7]
]

思路：

本体的解题思路其实就是进行层序遍历，将每层的节点放在一个vector数字当中，倘若根节点所在的层，我们定义为1的话，那么偶数层当中vector的元素要进行逆置。
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {//1.利用队列进行层序遍历//2.偶数层遍历逆置vector<vector<int>> result;if(root==nullptr){return result;}queue<TreeNode*> que;que.push(root);TreeNode* end=root;vector<int>  vv;int level=1;while(!que.empty()){TreeNode* tmp=que.front();que.pop();vv.push_back(tmp->val);if(tmp==end){if(level%2==0){reverse(vv.begin(),vv.end());}result.push_back(vv);vv.clear();++level;}if(tmp->left!=nullptr){que.push(tmp->left);}if(tmp->right!=nullptr){que.push(tmp->right);}if(tmp==end){end=que.back();}}return result;}

7.N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

链接:

/
// Definition for a Node.class Node {
public:int val;vector<Node*> children;
Node() {}
Node(int _val) {val = _val;}
Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
思路：

N叉树的层数遍历和二叉树的层序遍历主要思想其实是一致的；遍历二叉树的时候，我们需要遍历他们左右孩子；遍历N叉树的时候，其实遍历孩子就相当于访问vector数组
 vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> result;if(root==nullptr){return result;}queue<Node*> que;que.push(root);Node* end=root;vector<int> arr;while(!que.empty()){Node* tmp=que.front();que.pop();arr.push_back(tmp->val);for(int i=0;i<tmp->children.size();++i){if(tmp->children[i]!=nullptr)que.push(tmp->children[i]);}if(tmp==end){end=que.back();result.push_back(arr);arr.clear();}}return result;}