题目描述
102. 二叉树的层序遍历
给定一个二叉树，返回其按层序遍历得到的结点值。
解法1 递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
//处理输入空树
if (root == null) {
return new ArrayList<List<Integer>>();
}
CX(1, root, list);
return list;
}
public void CX(int level, TreeNode root, List<List<Integer>> list) {
//在二维数组相应位置添加一维数组，用于存放对应层的结点值。
//第一次进入函数时size = 0 < 1；在list 中添加存放第一层结点的数组，此后遍历过程中，充当在二位数组中添加数组的作用。list.size()是二维数组有多少个一位数组
if (list.size() < level) {
list.add(new ArrayList<Integer>());
}
//层数从1开始，二维数组从0开始，在相应层添加值
list.get(level - 1).add(root.val);
if (root.left != null) {
CX(level + 1, root.left, list);
}
if (root.right != null) {
CX(level + 1, root.right, list);
}
}
}
解法2 迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
//处理输入空
if(root == null){
return new ArrayList<List<Integer>>();
}
//将根结点加入队列，然后不断遍历队列
queue.add(root);
while (!queue.isEmpty()) {
//同一层的结点放入同一个数组
List<Integer> level = new ArrayList<>();
int n = queue.size();
//每完成一次0 ~ n 的for 循环，说明成功遍历了一层
for (int i = 0; i < n; i++) {
TreeNode curr = queue.poll();
level.add(curr.val);
//两个if 语句增加队列的长度，下一次从0 开始的for 循环时，队列里的元素数量刚好等于二叉树对应层的结点数量
if (curr.left != null) {
queue.add(curr.left);
}
if (curr.right != null) {
queue.add(curr.right);
}
}
list.add(level);
}
return list;
}
}
题目描述
给定一个二叉树，返回其结点值的锯齿形层次遍历。(即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行)。
103. 二叉树的锯齿形层次遍历
解法1 递归
与正常的层次遍历在偶数层(根结点为第一层)上不同，将正常的结果逆序即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
boolean isold = true;
//实施中会遇到在在队首添加元素，用LinkedList
List<List<Integer>> list = new LinkedList<List<Integer>>();
if (root == null) {
return list;
}
CX2(root, list, 1);
return list;
}
public void CX2(TreeNode curr, List<List<Integer>> list, int level) {
LinkedList<Integer> tmp = new LinkedList<>();
if (list.size() < level) {
list.add(new LinkedList<Integer>());
}
//奇数层正常添加，偶数层加在最前面
if (level % 2 == 1) {
list.get(level - 1).add(curr.val);
} else {
list.get(level - 1).add(0, curr.val);
}
if (curr.left != null) {
CX2(curr.left, list, level + 1);
}
if (curr.right != null) {
CX2(curr.right, list, level + 1);
}
}
}
解法2 迭代
维护一个队列，跟上面递归一样，注意顺序。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null){
return list;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 1;
//队列为空说明遍历完成
while(!queue.isEmpty()){
//申请一个临时数组存数
List<Integer> tmp = new LinkedList<>();
//实际 n 为每层的元素数量
int n = queue.size();
for(int i = 0; i < n ; i++){
TreeNode p = queue.remove();
if(level %2 == 1){
tmp.add(p.val);
}else{
//偶数层往数组最前方加数
tmp.add(0, p.val);
}
if( p.left != null){
queue.add(p.left);
}
if( p.right != null){
queue.add(p.right);
}
}
list.add(tmp);
level ++;
}
return list;
}
}
题目描述
给定一个二叉树，返回其节点值自底向上的层次遍历。(即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历)。
107. 二叉树的层次遍历 Ⅱ
解法1 递归
逆序正常层序遍历的结果
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
int depth = 1;
if (root == null) {
return list;
}
CX(root, list, depth);
Collections.reverse(list);
return list;
}
public void CX(TreeNode root, List<List<Integer>> list, int depth) {
int n = list.size();
if (n < depth) {
list.add(new ArrayList<Integer>());
}
list.get(depth - 1).add(root.val);
if (root.left != null) {
CX(root.left, list, depth + 1);
}
if (root.right != null) {
CX(root.right, list, depth + 1);
}
}
}
解法2 迭代
把正常层序遍历得到的结果逆序一下。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> list = new ArrayList();
if (root == null) {
return list;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
int n = queue.size();
List<Integer> a = new ArrayList<>();
for (int i = 0; i < n; i++) {
TreeNode tmp = queue.poll();
a.add(tmp.val);
if (tmp.left != null) {
queue.add(tmp.left);
}
if (tmp.right != null) {
queue.add(tmp.right);
}
}
list.add(a);
//或者 list.add(0,a);相应的list使用LinkedList
}
Collections.reverse(list);
return list;
}
}
题目描述
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
429. N叉树的层序遍历
解法 迭代
/*
// 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) {
LinkedList<Node> queue = new LinkedList<>();
List<List<Integer>> list = new ArrayList<>();
if (root == null) {
return list;
}
queue.add(root);
while (!queue.isEmpty()) {
ArrayList<Integer> tmp = new ArrayList<>();
int n = queue.size();
for (int i = 0; i < n; i++) {
Node node = queue.poll();
tmp.add(node.val);
queue.addAll(node.children);
}
list.add(tmp);
}
return list;
}
}
小结
二叉树的层序遍历和锯齿形层次遍历区别不大，锯齿形需要通过当前层数判断是否要逆序这一层的数组，上述两种实现采用在队首加数达到逆序的效果。
