/**
* Definition for a binary tree node.(LeetCode)
*/
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;
}
}
单源BFS:从某一个点开始(一个起点)。
多源BFS:从多个点同时开始走(多个起点)。
class Solution {
public boolean checkTree(TreeNode root) {
if( root.val == root.left.val + root.right.val )
return true;
else
return false;
}
}
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
// 遍历结果,注意题目输出格式
List<List<Integer>> traverseResult = new LinkedList<>();
// 根节点为空的情况
if ( root == null )
return traverseResult;
// BFS,使用队列
Queue<TreeNode> queue = new LinkedList<>();
// 前面判断了根节点为空,这里根节点入队列
queue.add(root);
// 借助队列层序遍历二叉树,直到所有节点出列
while( !queue.isEmpty() ) {
// 每层节点个数
int levelCount = queue.size();
// 该层每个节点值
List<Integer> levelResult = new ArrayList<>();
// 遍历该层节点
for (int i=0; i<levelCount; i++) {
// 队头节点出队列
TreeNode node = queue.poll();
// 出列节点值,加入List集合
levelResult.add(node.val);
// 左节点存在,入队
if ( node.left != null ) {
queue.add( node.left );
}
// 右节点存在,入队
if ( node.right != null ) {
queue.add( node.right );
}
}
// 该层遍历结果
traverseResult.add( levelResult );
}
return traverseResult;
}
}
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
// 遍历结果,注意题目输出格式、自底向上
List<List<Integer>> traverseResult = new LinkedList<>();
// 根节点为空的情况
if ( root == null )
return traverseResult;
// BFS,使用队列
Queue<TreeNode> queue = new LinkedList<>();
// 前面判断了根节点为空,这里根节点入队列
queue.add(root);
// 借助队列层序遍历二叉树,直到所有节点出列
while( !queue.isEmpty() ) {
// 每层节点个数
int levelCount = queue.size();
// 该层每个节点值
List<Integer> levelResult = new ArrayList<>();
// 遍历该层节点
for ( int i=0; i<levelCount; i++ ) {
// 队头节点出队列
TreeNode node = queue.poll();
// 出列节点值,加入List集合
levelResult.add(node.val);
// 左节点存在,入队
if ( node.left != null )
queue.add(node.left);
// 右节点存在,入队
if ( node.right != null )
queue.add(node.right);
}
// 该层遍历结果,将存储该层节点值的列表添加到结果列表的头部。
traverseResult.add(0,levelResult);
}
return traverseResult;
}
}
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> traverseResult = new LinkedList<>();
if ( root == null )
return traverseResult;
// BFS层序遍历,双端队列实现输出顺序交替
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// true时从左往右,false时从右往左
boolean flag = true;
while( !queue.isEmpty() ) {
int levelCount = queue.size();
// 双端队列
LinkedList<Integer> levelResult = new LinkedList<>();
for(int i=0; i<levelCount; i++) {
TreeNode node = queue.poll();
// 从左往右,插入双端队列末尾
if(flag)
levelResult.offerLast(node.val);
// 从右往左,插入双端队列头部
else
levelResult.offerFirst(node.val);
if ( node.left != null)
queue.offer(node.left);
if ( node.right != null )
queue.offer(node.right);
}
traverseResult.add(levelResult);
// 每层遍历完,修改标记
flag = !flag;
}
return traverseResult;
}
}
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> avgResult = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while( !queue.isEmpty() ) {
int levelCount = queue.size();
double levelSum = 0;
for(int i=0; i<levelCount; i++) {
TreeNode node = queue.poll();
levelSum += node.val;
if ( node.left != null )
queue.offer(node.left);
if ( node.right != null )
queue.offer(node.right);
}
avgResult.add( levelSum / levelCount );
}
return avgResult;
}
}
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> rightResult = new ArrayList<>();
if ( root == null )
return rightResult;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while ( !queue.isEmpty() ) {
int levelCount = queue.size();
for(int i=0; i<levelCount; i++) {
TreeNode node = queue.poll();
// 每层最右侧节点
if ( node.left != null )
queue.offer(node.left);
if ( node.right != null )
queue.offer(node.right);
if (i+1 == levelCount)
rightResult.add(node.val);
}
}
return rightResult;
}
}
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int bottomLeft = root.val;
while ( !queue.isEmpty() ) {
int levelCount = queue.size();
for(int i=0; i<levelCount; i++) {
TreeNode node = queue.poll();
// 每层最左边节点的值
if ( i == 0 )
bottomLeft = node.val;
if ( node.left != null )
queue.offer(node.left);
if ( node.right != null )
queue.offer(node.right);
}
}
// 层序遍历,bottomLeft是最后一层最左边节点的值
return bottomLeft;
}
}
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> largestResult = new LinkedList<>();
if ( root == null )
return largestResult;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while ( !queue.isEmpty() ) {
int levelCount = queue.size();
int maxValue = Integer.MIN_VALUE;
for(int i=0; i<levelCount; i++) {
TreeNode node = queue.poll();
if ( maxValue < node.val )
maxValue = node.val;
if ( node.left != null )
queue.offer(node.left);
if ( node.right != null )
queue.offer(node.right);
}
largestResult.add(maxValue);
}
return largestResult;
}
}
class Solution {
public int maxLevelSum(TreeNode root) {
int maxLevel = 1;
int maxSum = Integer.MIN_VALUE;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 1;
while ( !queue.isEmpty() ) {
int levelCount = queue.size();
int levelSum = 0;
for(int i=0; i<levelCount; i++) {
TreeNode node = queue.poll();
levelSum += node.val;
if ( node.left != null )
queue.offer(node.left);
if ( node.right != null )
queue.offer(node.right);
}
if ( levelSum > maxSum ) {
maxLevel = level;
maxSum = levelSum;
}
level += 1;
}
return maxLevel;
}
}
class Solution {
public boolean isSymmetric(TreeNode root) {
// BFS做法
if ( root == null )
return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while( !queue.isEmpty() ) {
int levelCount = queue.size();
LinkedList<Integer> leftResult = new LinkedList<>();
LinkedList<Integer> rightResult = new LinkedList<>();
// 每层循环遍历,从左往右、从右往左的结果是否相等
for(int i=0; i<levelCount; i++) {
TreeNode node = queue.poll();
// 节点值范围 -100 ~ 100,空节点可用极大或极小值填充
if ( node == null ) {
leftResult.offerLast(-1000);
rightResult.offerFirst(-1000);
}
else {
leftResult.offerLast(node.val);
rightResult.offerFirst(node.val);
queue.offer(node.left);
queue.offer(node.right);
}
}
// 每层从左往右、从右往左的结果是否相等,空节点用缺省值填充
if (leftResult.equals(rightResult))
continue;
else
return false;
}
return true;
}
}
class Solution {
public int deepestLeavesSum(TreeNode root) {
int sumResult = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while( !queue.isEmpty() ) {
int levelCount = queue.size();
int levelSum = 0;
for ( int i=0; i<levelCount; i++ ) {
TreeNode node = queue.poll();
levelSum += node.val;
if ( node.left != null )
queue.offer(node.left);
if ( node.right != null )
queue.offer(node.right);
}
sumResult = levelSum;
}
return sumResult;
}
}