二叉树的层序遍历
广度优先搜索
我们可以用一种巧妙的方法修改广度优先搜索：
- 首先根元素入队
- 当队列不为空的时候
- 1.求当前队列的长度 Si
2.依次从队列中取 Si 个元素进行拓展，然后进入下一次迭代
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { //初始化队列同时将第一层节点加入队列中，即根节点 queue<TreeNode*> az; vector<vector<int>> sz; if(root==nullptr) { return sz; } az.push(root); //外层的while循环迭代的是层数 while(!az.empty()) { //记录当前队列大小 int size=az.size(); vector<int> a; //遍历这一层的所有节点 for(int i=0;i<size;i++) { //从队首取出元素 TreeNode* node=az.front(); az.pop(); a.push_back(node->val); if(node->left) az.push(node->left); if(node->right)az.push(node->right); } sz.push_back(a); } return sz; } };
大家请记住这个模板,后面的几个练习题，都是在这个上面稍作更改.
二叉树的层序遍历II
相对于上面的题目，我们就需要把数组翻转一下就好了.
class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> az; queue<TreeNode*> sz; if(root==nullptr) { return az; } sz.push(root); while(!sz.empty()) { vector<int> a; int size=sz.size(); for(int i=0;i<size;i++) { TreeNode* node=sz.front(); sz.pop(); a.push_back(node->val); if(node->left) sz.push(node->left); if(node->right) sz.push(node->right); } az.push_back(a); } reverse(az.begin(),az.end()); return az; } };
二叉树的右视图
层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> az; queue<TreeNode*> sz; if(root==nullptr) { return az; } sz.push(root); while(!sz.empty()) { int size=sz.size(); for(int i=0;i<size;i++) { TreeNode* node=sz.front(); sz.pop(); if(i==size-1) { az.push_back(node->val); } if(node->left)sz.push(node->left); if(node->right)sz.push(node->right); } } return az; } };
二叉树的层平均值
本题就是层序遍历的时候把一层求个总和在取一个均值。
class Solution { public: vector<double> averageOfLevels(TreeNode* root) { vector<double> az; queue<TreeNode*> sz; if(root==nullptr) { return az; } sz.push(root); while(!sz.empty()) { double sum=0; int size=sz.size(); for(int i=0;i<size;i++) { TreeNode* node=sz.front(); sz.pop(); sum+=node->val; if(node->left)sz.push(node->left); if(node->right)sz.push(node->right); } az.push_back(sum/size); } return az; } };
N叉树的层序遍历
这题就是跟第一题基本一样的，只不过节点多了几个孩子
class Solution { public: vector<vector<int>> levelOrder(Node* root) { vector<vector<int>> az; queue<Node*> sz; if(root==nullptr){ return az; } sz.push(root); while(!sz.empty()) { vector<int> a; int size=sz.size(); for(int i=0;i<size;i++) { Node* node=sz.front(); sz.pop(); a.push_back(node->val); for(int i=0;i<node->children.size();i++) { if(node->children[i]) sz.push(node->children[i]); } } az.push_back(a); } return az; } };
在每个树行中找最大值
class Solution { public: vector<int> largestValues(TreeNode* root) { vector<int> az; queue<TreeNode*> sz; if(root==nullptr) { return az; } sz.push(root); while(!sz.empty()) { int size=sz.size(); int max=INT_MIN; for(int i=0;i<size;i++) { TreeNode* node=sz.front(); sz.pop(); max=max>node->val?max:node->val; if(node->left) sz.push(node->left); if(node->right)sz.push(node->right); } az.push_back(max); } return az; } };
填充每个节点的下一个右侧节点指针
回想一下二叉树的层次遍历，用广度优先实现的时候，就是层层遍历，每层临时遍历的节点都会放到一个队列中。队列中保存了第 i 层节点的信息，我们利用这个特点，将队列中的元素都串联一遍就可以了。
class Solution { public Node connect(Node root) { if (root == null) { return root; } // 初始化队列同时将第一层节点加入队列中，即根节点 Queue<Node> queue = new LinkedList<Node>(); queue.add(root); // 外层的 while 循环迭代的是层数 while (!queue.isEmpty()) { // 记录当前队列大小 int size = queue.size(); // 遍历这一层的所有节点 for (int i = 0; i < size; i++) { // 从队首取出元素 Node node = queue.poll(); // 连接 if (i < size - 1) { node.next = queue.peek(); } // 拓展下一层节点 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } } // 返回根节点 return root; } }
填充每个节点的下一个右侧节点指针II
和上题是完全一样的
class Solution { public: Node* connect(Node* root) { if (root == nullptr) { return root; } // 初始化队列同时将第一层节点加入队列中，即根节点 queue<Node*> Q; Q.push(root); // 外层的 while 循环迭代的是层数 while (!Q.empty()) { // 记录当前队列大小 int size = Q.size(); // 遍历这一层的所有节点 for(int i = 0; i < size; i++) { // 从队首取出元素 Node* node = Q.front(); Q.pop(); // 连接 if (i < size - 1) { node->next = Q.front(); } // 拓展下一层节点 if (node->left != nullptr) { Q.push(node->left); } if (node->right != nullptr) { Q.push(node->right); } } } // 返回根节点 return root; } };
二叉树的最大深度
这题前面有讲过， 可以参考这篇博客:力扣刷题之二叉树的最大深度_skeet follower的博客-CSDN博客
二叉树的最小深度
需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点
class Solution { public: int minDepth(TreeNode* root) { queue<TreeNode*> az; if(root==nullptr) { return 0; } int depth=0; az.push(root); while(!az.empty()) { int size=az.size(); depth++; for(int i=0;i<size;i++) { TreeNode* node=az.front(); az.pop(); if(node->left) az.push(node->left); if(node->right)az.push(node->right); if(node->right==nullptr&&node->left==nullptr) { return depth; } } } return depth; } };
