BFS广度优先搜索 #
一、二叉树的层序遍历 #
102.二叉树的层序遍历 #
题目地址:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
107.二叉树的层次遍历 II #
题目链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
- 相对于102.二叉树的层序遍历,就是最后把result数组反转一下就可以了。
199.二叉树的右视图 #
题目链接:https://leetcode-cn.com/problems/binary-tree-right-side-view/
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
- 层序遍历的时候,判断是否遍历到单层的最后面的元素
637.二叉树的层平均值 #
题目链接:https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
- 层序遍历的时候把一层求个总和在取一个均值。
429.N叉树的层序遍历 #
题目链接:https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。
- 多个孩子
for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列
if (node->children[i]) que.push(node->children[i]);
}
515.在每个树行中找最大值 #
题目链接:https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
您需要在二叉树的每一行中找到最大的值。
- 层序遍历,取每一层的最大值
116.填充每个节点的下一个右侧节点指针 #
题目链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。
- 单层遍历的时候记录一下本层的头部节点,然后在遍历的时候让前一个节点指向本节点
117.填充每个节点的下一个右侧节点指针II #
题目地址:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
普通二叉树。一样
104.二叉树的最大深度 #
题目地址:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数
111.二叉树的最小深度 #
相对于 104.二叉树的最大深度 ,本题还也可以使用层序遍历的方式来解决,思路是一样的。
- 只有当左右孩子都为空的时候,才说明遍历的最低点了。如果其中一个孩子为空则不是最低点