目录
102.二叉树的层序遍历
107.二叉树的层序遍历II
199.二叉树的右视图
637.二叉树的层平均值
429.N叉树的层序遍历
501.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最大深度
102.二叉树的层序遍历
题目
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]
代码(队列实现)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//res保存每一层的结果集
List<List<Integer>> res = new ArrayList<List<Integer>>();
//如果根节点为空,直接返回
if(root == null){
return res;
}
//que队列,用来保存访问过但还没处理的节点
Queue<TreeNode> que = new ArrayDeque<>();
que.offer(root); //根节点入队,队列有一个节点
//当队列非空,说明还有节点没处理
while(!que.isEmpty()){
int len = que.size(); //当前队列长度就是这一层的元素个数
List<Integer> tmpRes = new ArrayList<>(); //用来保存这一层的结果值
//逐个处理这一层的每个节点
while(len > 0){
TreeNode tmp = que.poll(); //出队
tmpRes.add(tmp.val); //加入暂时结果集
//左孩子进队
if(tmp.left != null){
que.offer(tmp.left);
}
//右孩子进队
if(tmp.right != null){
que.offer(tmp.right);
}
len--;
}
res.add(tmpRes); //加入单层结果集
}
return res;
}
}
总结
二叉树层序遍历,核心思想是要用队列把已经遍历过的节点入队,然后在处理节点时,再把该处理节点的左右子节点入队。一定要理解,其实二叉树的层序遍历是一层一层处理的,每次的len都是当前队列的长度,代表当前层的结点个数,然后依次出队处理,并遍历其左右子节点。
107.二叉树的层序遍历II
题目
给你二叉树的根节点 root
,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[15,7],[9,20],[3]]
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
//res保存每一层的结果集
List<List<Integer>> res = new ArrayList<List<Integer>>();
//如果根节点为空,直接返回
if(root == null){
return res;
}
//que队列,用来保存访问过但还没处理的节点
Queue<TreeNode> que = new ArrayDeque<>();
que.offer(root); //根节点入队,队列有一个节点
//当队列非空,说明还有节点没处理
while(!que.isEmpty()){
int len = que.size(); //当前队列长度就是这一层的元素个数
List<Integer> tmpRes = new ArrayList<>(); //用来保存这一层的结果值
//逐个处理这一层的每个节点
while(len > 0){
TreeNode tmp = que.poll(); //出队
tmpRes.add(tmp.val); //加入暂时结果集
//左孩子进队
if(tmp.left != null){
que.offer(tmp.left);
}
//右孩子进队
if(tmp.right != null){
que.offer(tmp.right);
}
len--;
}
res.add(tmpRes); //加入单层结果集
}
//把自顶而下的层序遍历逆序
List<List<Integer>> lastres = new ArrayList<List<Integer>>();
for(int i = res.size()-1; i >= 0; i--){
lastres.add(res.get(i));
}
return lastres;
}
}
总结
二叉树自底而上的层序遍历,就是在最基本的二叉树层序遍历的基础上,把最后的result反转一下。
199.二叉树的右视图
题目
给定一个二叉树的 根节点 root
,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
//res保存每一层的结果集
List<List<Integer>> res = new ArrayList<List<Integer>>();
//保存返回结果
List<Integer> lastres = new ArrayList<>();
//如果根节点为空,直接返回
if(root == null){
return lastres;
}
//que队列,用来保存访问过但还没处理的节点
Queue<TreeNode> que = new ArrayDeque<>();
que.offer(root); //根节点入队,队列有一个节点
//当队列非空,说明还有节点没处理
while(!que.isEmpty()){
int len = que.size(); //当前队列长度就是这一层的元素个数
List<Integer> tmpRes = new ArrayList<>(); //用来保存这一层的结果值
//逐个处理这一层的每个节点
while(len > 0){
TreeNode tmp = que.poll(); //出队
tmpRes.add(tmp.val); //加入暂时结果集
//左孩子进队
if(tmp.left != null){
que.offer(tmp.left);
}
//右孩子进队
if(tmp.right != null){
que.offer(tmp.right);
}
len--;
}
res.add(tmpRes); //加入单层结果集
}
//返回每一次的最右(最后)元素
for(int i=0; i < res.size(); i++){
List<Integer> tmpRes = res.get(i);
lastres.add(tmpRes.get(tmpRes.size()-1));
}
return lastres;
}
}
637.二叉树的层平均值
题目
给定一个非空二叉树的根节点 root
, 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5
以内的答案可以被接受。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[3.00000,14.50000,11.00000] 解释:第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11]
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
//res保存层序遍历结果
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Double> lastres = new ArrayList<>();
//如果根节点为空,直接返回
if(root == null){
return lastres;
}
//que队列,用来保存访问过但还没处理的节点
Queue<TreeNode> que = new ArrayDeque<>();
que.offer(root); //根节点入队,队列有一个节点
//当队列非空,说明还有节点没处理
while(!que.isEmpty()){
int len = que.size(); //当前队列长度就是这一层的元素个数
List<Integer> tmpRes = new ArrayList<>(); //用来保存这一层的结果值
//逐个处理这一层的每个节点
while(len > 0){
TreeNode tmp = que.poll(); //出队
tmpRes.add(tmp.val); //加入暂时结果集
//左孩子进队
if(tmp.left != null){
que.offer(tmp.left);
}
//右孩子进队
if(tmp.right != null){
que.offer(tmp.right);
}
len--;
}
res.add(tmpRes); //加入单层结果集
}
//计算每一层的平均值
for(int i = 0; i < res.size(); i++){
List<Integer> tmplist = res.get(i);
double sum = 0;
for(int j=0; j < tmplist.size(); j++){
sum += tmplist.get(j);
}
lastres.add(sum/tmplist.size());
}
return lastres;
}
}
429.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;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> list = new ArrayList<>();
Queue<Node> que = new ArrayDeque<>();
if(root == null){
return list;
}
//根节点入队
que.offer(root);
//当队列非空,就一层一层处理
while(!que.isEmpty()){
//保存单层遍历处理节点值
List<Integer> levelList = new ArrayList<>();
int size = que.size();//队列大小=当前层的结点个数
while(size-- > 0){
Node tmp = que.poll(); //队头出队
levelList.add(tmp.val); //处理队头
//把处理节点的子节点全部入队
for(Node node : tmp.children){
if(node != null){
que.offer(node);
}
}
}
list.add(levelList);
}
return list;
}
}
501.在每个树行中找最大值
题目
给定一棵二叉树的根节点 root
,请找出该二叉树中每一层的最大值。
示例1:
输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
//保存每一层的最大值
List<Integer> result = new ArrayList<>();
//队列
Queue<TreeNode> que = new ArrayDeque<>();
if(root == null){
return result;
}
//根节点入队
que.offer(root);
//队列非空,就一层层处理
while(!que.isEmpty()){
int max = Integer.MIN_VALUE;
int size = que.size(); //队列大小=当前层的大小
//遍历当前层的节点
while(size-- > 0){
TreeNode tmp = que.poll();
int val = tmp.val;
if(max < val){
max = val;
}
//左右子节点入队
if(tmp.left != null){
que.offer(tmp.left);
}
if(tmp.right != null){
que.offer(tmp.right);
}
}
result.add(max);
}
return result;
}
}
116.填充每个节点的下一个右侧节点指针
题目
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL
。
初始状态下,所有 next 指针都被设置为 NULL
。
示例 1:
输入:root = [1,2,3,4,5,6,7] 输出:[1,#,2,3,#,4,5,6,7,#]
代码
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
Queue<Node> que = new ArrayDeque<>();
if(root == null){
return root;
}
//根节点入队
que.offer(root);
//队列非空,一层层处理
while(!que.isEmpty()){
int size = que.size();
//cur指向每一层的第一个节点,先处理其孩子进队
Node cur = que.poll();
if(cur.left != null){
que.offer(cur.left);
}
if(cur.right != null){
que.offer(cur.right);
}
//处理同一层后面的节点,指向next
for(int i=1; i < size; i++){
Node next = que.poll();
if(next.left != null){
que.offer(next.left);
}
if(next.right != null){
que.offer(next.right);
}
//打指针,指向右边节点
cur.next = next;
//cur右移
cur = next;
}
}
return root;
}
}
117.填充每个节点的下一个右侧节点指针II
题目
给定一个二叉树:
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL
。
初始状态下,所有 next 指针都被设置为 NULL
。
示例 1:
输入:root = [1,2,3,4,5,null,7] 输出:[1,#,2,3,#,4,5,7,#]
代码
和116一模一样。
104.二叉树的最大深度
题目
给定一个二叉树 root
,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
//队列
Queue<TreeNode> que = new ArrayDeque<>();
//初始化深度
int depth = 0;
if(root == null){
return depth;
}
//根节点入队
que.offer(root);
while(!que.isEmpty()){
int size = que.size();
while(size -- > 0){
//这一层的一个个出队
TreeNode tmp = que.poll();
//处理左右子节点
if(tmp.left != null){
que.offer(tmp.left);
}
if(tmp.right != null){
que.offer(tmp.right);
}
}
depth++;
}
return depth;
}
}
111.二叉树的最小深度
题目
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:2
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
Queue<TreeNode> que = new ArrayDeque<>();
int depth = 0;
if(root == null){
return 0;
}
que.offer(root);
//当队列非空,就一层层处理
while(!que.isEmpty()){
int size = que.size();
//处理当前层,depth+1
depth++;
//遍历这一层的每一个元素
while(size-- > 0){
TreeNode tmp = que.poll();
//如果该节点的左右节点都为空,说明到的最小深度
if(tmp.left == null && tmp.right == null){
return depth;
}
if(tmp.left != null){
que.offer(tmp.left);
}
if(tmp.right != null){
que.offer(tmp.right);
}
}
}
return depth;
}
}