二叉树的层次遍历(10道)

2024-09-07 09:04
文章标签 二叉树 遍历 层次

本文主要是介绍二叉树的层次遍历(10道),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

(写给未来遗忘的自己)

102.二叉数的层序遍历(从上到下)

题目:

代码:

class Solution {  
public:  vector<vector<int>> levelOrder(TreeNode* root) {  vector<vector<int>> result;  queue<TreeNode*> node;  if (root == nullptr) {  return result;  }  node.push(root);  //这个是一层执行一次while (!node.empty()) {  int node_size = node.size();  vector<int> layer_result;  //处理横着一列的数据for (int i = 0; i < node_size; i++) {  TreeNode* root_t = node.front();  node.pop();  layer_result.push_back(root_t->val);  if (root_t->left != nullptr) {  node.push(root_t->left);  }  if (root_t->right != nullptr) {  node.push(root_t->right);  }  }  result.push_back(layer_result);  }  return result;  }  
};

思路:

 107.二叉树的层序遍历Ⅱ(从下往上遍历)

题目:

代码: 

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>>result;std::queue<TreeNode*>node;std::stack<vector<int>>result_uptodown;if(root==nullptr) return result;node.push(root);while(!node.empty()){int layer_size=node.size();vector<int>layer_result;for(int i=0;i<layer_size;i++){TreeNode* root_t=node.front();node.pop();layer_result.push_back(root_t->val);if(root_t->left!=nullptr) node.push(root_t->left);if(root_t->right!=nullptr) node.push(root_t->right);}result_uptodown.push(layer_result);}while(!result_uptodown.empty()){result.push_back(result_uptodown.top());result_uptodown.pop();}return result;}
};

思路:

整体思路和上面一样。但是我们需要的是从下到上的。

stack实现的是先进后出的机制。所以我们在第一个案例的实现的时候一层的数vector<int>layer_result的数据不要直接push_back在result中,经过一个stack<vector<int>>,这样最下层的最先弹出。 

 199.二叉树的右视图:

题目:

代码:

class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int>result;std::queue<TreeNode*>node;if(root==nullptr) return result;node.push(root);while(!node.empty()){int layer_size=node.size();vector<int>layer_result;for(int i=0;i<layer_size;i++){TreeNode* root_t=node.front();node.pop();layer_result.push_back(root_t->val);if(root_t->left!=nullptr) node.push(root_t->left);if(root_t->right!=nullptr) node.push(root_t->right);}result.push_back(layer_result[layer_size-1]);}return result;}
};

思路:

主代码的逻辑一致,只是最后的结果存入只要层的vector的最后一位。

637.二叉树的层平均值

题目:

代码:

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<double>restlt;std::queue<TreeNode*>node;node.push(root);while(!node.empty()){int layer_size=node.size();double sum=0;for(int i=0;i<layer_size;i++){TreeNode*root_t=node.front();node.pop();sum=sum+root_t->val;if(root_t->left!=nullptr) node.push(root_t->left);if(root_t->right!=nullptr) node.push(root_t->right);}restlt.push_back(sum/layer_size);}return restlt;}
};

思路:

在for循环中累加和,然后加入result的时候求平均值。

429.N叉树的层序遍历

题目:

代码:

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>>result;queue<Node*>node;if(root==nullptr) return result;node.push(root);while(!node.empty()){int layer_size=node.size();vector<int>layer_result;for(int i=0;i<layer_size;i++){Node* root_t=node.front();node.pop();layer_result.push_back(root_t->val);for(auto it:root_t->children){node.push(it);}}result.push_back(layer_result);}return result;}
};

思路:

N叉树和二叉树的区别在于存储子节点的方式为:

vector<node*>children

所以在存储新的数据进去的时候不能用原来的方式,需要换成for循环遍历vector

//二叉数
if(root_t->left!=nullptr) node.push(root_t->left);
if(root_t->right!=nullptr) node.push(root_t->right);//N叉树
for(auto it:root_t->children){node.push(it);}

 515.在每一个树行中找到最大值

题目:

代码: 

class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int>result;queue<TreeNode*>node;if(root==nullptr) return result;node.push(root);while(!node.empty()){int layer_size=node.size();int layer_max=std::numeric_limits<int>::min();for(int i=0;i<layer_size;i++){TreeNode* root_t=node.front();node.pop();if(root_t->val>layer_max){layer_max=root_t->val;}if(root_t->left!=nullptr) node.push(root_t->left);if(root_t->right!=nullptr) node.push(root_t->right);}result.push_back(layer_max);}return result;   }};

思路和知识点:

每一行找最大值

初始值的定义最小值:

std::numeric_limits<int>::min();

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

题目:

代码:

class Solution {
public:Node* connect(Node* root) {Node* result=root;std::queue<Node*>node;if(root==nullptr) return result;node.push(root);while(!node.empty()){int layer_size=node.size();for(int i=0;i<layer_size;i++){Node* root_first=node.front();node.pop();Node* root_second=node.front();if(root_first->left!=nullptr) node.push(root_first->left);if(root_first->right!=nullptr) node.push(root_first->right);if(i==layer_size-1){root_first->next=NULL;}else {root_first->next=root_second;}}}return result;}
};

思路:

整体的层次遍历和上面的处理一样。

重写代码在于怎么实现指向下一个的语句。

Node* root_first=node.front();
node.pop();
Node* root_second=node.front();if(i==layer_size-1){root_first->next=NULL;}else {root_first->next=root_second;}

队列中取完当前元素后的第一个元素就是我们需要next指向的,所以我们只取使用,不弹出。

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

题目:

这道题和上一道题的区别在于一个是完全二叉树,一个不是。但是代码的逻辑没有按照这个做刻意的处理,所以代码一样。 

104.二叉树的最大深度

题目:

代码:

class Solution {
public:int maxDepth(TreeNode* root) {int result=0;std::queue<TreeNode*>node;if(root==nullptr) return result;node.push(root);while(!node.empty()){int layer_size=node.size();for(int i=0;i<layer_size;i++){TreeNode* root_t=node.front();node.pop();if(root_t->left!=nullptr) node.push(root_t->left);if(root_t->right!=nullptr) node.push(root_t->right);}result++;}return result;}
};

111.二叉树的最小深度:

题目:

 代码:

class Solution {  
public:  int minDepth(TreeNode* root) {  int result = 1; std::queue<TreeNode*> nodeQueue;  if (root == nullptr) return 0; nodeQueue.push(root); while (!nodeQueue.empty()) {  int layerSize = nodeQueue.size(); for (int i = 0; i < layerSize; i++) {  TreeNode* currentNode = nodeQueue.front();   nodeQueue.pop(); if (currentNode->left == nullptr && currentNode->right == nullptr)  return result; if (currentNode->left != nullptr)   nodeQueue.push(currentNode->left);  if (currentNode->right != nullptr)   nodeQueue.push(currentNode->right);   }   result++;  }  return result;}  
};

思路:

最浅就是:一个节点没有任何的子节点的时候就是最浅

这篇关于二叉树的层次遍历(10道)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1144644

相关文章

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

1、绑定属性 constructor(){super()this.state={name:"张三",title:'我是一个title'}}render() {return (<div><div>aaaaaaa{this.state.name}<div title={this.state.title}>我是一个title</div></div></div>)} 绑定属性直接使用花括号{}   注

MATLAB层次聚类分析法

转自:http://blog.163.com/lxg_1123@126/blog/static/74841406201022774051963/ 层次聚类是基于距离的聚类方法,MATLAB中通过pdist、linkage、dendrogram、cluster等函数来完成。层次聚类的过程可以分这么几步: (1) 确定对象(实际上就是数据集中的每个数据点)之间的相似性,实际上就是定义一个表征

在二叉树中找到两个节点的最近公共祖先(基于Java)

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo

数据结构--二叉树(C语言实现,超详细!!!)

文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念 二叉树(Binary Tree)是数据结构中一种非常重要的树形结构,它的特点是每个节点最多有两个子节点,通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具

hashmap的存值,各种遍历方法

package com.jefflee;import java.util.HashMap;import java.util.Iterator;import java.util.Map;public class HashmapTest {// 遍历Hashmap的四种方法public static void main(String[] args) {//hashmap可以存一个null,把

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历,在uva上找了个题敲了出来,感觉还不错,最近敲代码挺有手感的,希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

222.完全二叉树的节点个数

(写给未来遗忘的自己) 题目: 代码: class Solution {public:int countNodes(TreeNode* root) {queue<TreeNode*>node_que;if(root==nullptr) return 0;node_que.push(root);int result;while(!node_que.empty()){int layer_s