树的层序遍历
目录
1 N叉树的层序遍历 （递归法）
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :
返回其层序遍历:
[
[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,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
public class levelOrder {
public static void main(String[] args) {
}
static List<List<Integer>> returnList = new ArrayList<>();
public static List<List<Integer>> levelOrder(Node root) {
if(root == null){
return returnList;
}
if(root.children == null){
returnList.get(0).add(root.val);
return returnList;
}
helper(root,0);
return returnList;
}
private static void helper(Node root,int index) {
if (returnList.size() == index) {
returnList.add(new ArrayList<>());
}
returnList.get(index).add(root.val);
for (int i = 0; i <root.children.size() ; i++) {
helper(root.children.get(i),index +1);
}
}
}
队列（广度优先遍历）
public static void main(String[] args) {
Node node2 = new Node();
node2.val = 2;
Node node4 = new Node();
node4.val = 4;
Node node5 = new Node();
node5.val = 5;
Node node6 = new Node();
node6.val = 6;
List<Node> Node2 = new ArrayList<>();
Node2.add(node5);
Node2.add(node6);
Node node3 = new Node(3,Node2);
List<Node> Node1 = new ArrayList<>();
Node1.add(node3);
Node1.add(node2);
Node1.add(node4);
Node node1 = new Node(1,Node1 );
System.out.println(levelOrder(node1));
// List<List<Integer>> returnList = levelOrder(node1);
// for (int i = 0; i <returnList.size() ; i++) {
// for (int j = 0; j <returnList.get(i).size() ; j++) {
// System.out.print(returnList.get(i).get(j));
// }
// }
}
public static List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int count = queue.size();
//外层循环为一层
List<Integer> list = new ArrayList<>();
while (count-- > 0) {
//将当前元素的非空子节点压入栈
Node cur = queue.poll();
list.add(cur.val);
if(cur.children != null){
for (Node node : cur.children) {
if (node != null) {
queue.add(node);
}
}
}
}
res.add(list);
}
return res;
}
}
2 二叉树的锯齿形层次遍历（dfs 队列 BFS）
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
dfs
public class zigzagLevelOrder {
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
TreeNode node1 = new TreeNode(9);
TreeNode node2 = new TreeNode(20);
TreeNode node3 = new TreeNode(15);
TreeNode node4 = new TreeNode(7);
root.left=node1;
root.right=node2;
node2.left=node3;
node2.right=node4;
List<List<Integer>> returnLevels =zigzagLevelOrder(root);
for(int i =0;i<returnLevels.size();i++){
for(int j =0;j<returnLevels.get(i).size();j++){
System.out.print(returnLevels.get(i).get(j)+" ");
}
System.out.println();
}
}
static List<List<Integer>> levels = new ArrayList<>();
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null){
return levels;
}
helper(root, 0);
return levels;
}
private static void helper(TreeNode node, int level) {
if (node == null) {
return;
}
if (levels.size() == level) {
levels.add(new ArrayList<>());
}
if(level % 2 ==0){
levels.get(level).add(node.val);
}else {
levels.get(level).add(0,node.val);
}
helper(node.left, level + 1);
helper(node.right, level + 1);
}
}
bfs
/**
* 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>> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
int depth = 0;
while (!queue.isEmpty()) {
List<Integer> tmp = new LinkedList<>();
int cnt = queue.size();
for (int i = 0; i < cnt; i++) {
TreeNode node = queue.poll();
// System.out.println(node.val);
if (depth % 2 == 0) tmp.add(node.val);
else tmp.add(0, node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
res.add(tmp);
depth++;
}
return res;
}
}
3二叉树的层次遍历（递归法 队列 BFS）
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
思路 递归
public class Main {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(3);
TreeNode node3 = new TreeNode(4);
TreeNode node4 = new TreeNode(5);
root.left=node1;
root.right=node2;
node1.left=node3;
node2.right=node4;
levelOrder(root);
for(int i =0;i<levels.size();i++){
for(int j =0;j<levels.get(i).size();j++){
System.out.print(levels.get(i).get(j)+" ");
}
System.out.println();
}
System.out.println("Hello World!");
}
static List<List<Integer>> levels = new ArrayList<>();
public static List<List<Integer>> levelOrder(TreeNode root) {
if (root == null){
return levels;
}
helper(root, 0);
return levels;
}
public static void helper(TreeNode node, int level) {
// start the current level
if (levels.size() == level) {
levels.add(new ArrayList<>());
//一定要注意这里的结束条件是levels.size() == level
}
// fulfil the current level
levels.get(level).add(node.val);
// process child nodes for the next level
if (node.left != null) {
helper(node.left, level + 1);
}
if (node.right != null){
helper(node.right, level + 1);
}
}
}
思路 队列(还没看懂)
public class Test1 {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(3);
TreeNode node3 = new TreeNode(4);
TreeNode node4 = new TreeNode(5);
root.left=node1;
root.right=node2;
node1.left=node3;
node2.right=node4;
levelOrder(root);
System.out.println(levelOrder(root));
}
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<List<Integer>>();
if (root == null) return levels;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int level = 0;
while ( !queue.isEmpty() ) {
// start the current level
levels.add(new ArrayList<Integer>());
//还有这里必须要进行初始化
// number of elements in the current level
//这里要提前记住level_length，因为在循环里面会直接加上
int level_length = queue.size();
for(int i = 0; i < level_length; ++i) {
TreeNode node = queue.poll();
//一定要注意是这里是remove不是poll
// fulfill the current level
levels.get(level).add(node.val);
// add child nodes of the current level
// in the queue for the next level
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
// go to next level
level++;
}
return levels;
}
}
4 二叉树的层次遍历（DFS BFS）
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为：
[
[15,7],
[9,20],
[3]
]
dfs
import java.util.ArrayList;
import java.util.List;
/**
* @Auther: liuhaidong
* Data: 2019/10/15 0015、16:01
* Description:
* @version: 1.0
*/
public class levelOrderBottom {
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
TreeNode node1 = new TreeNode(9);
TreeNode node2 = new TreeNode(20);
TreeNode node3 = new TreeNode(15);
TreeNode node4 = new TreeNode(7);
root.left=node1;
root.right=node2;
node2.left=node3;
node2.right=node4;
levelOrderBottom(root);
for(int i =0;i<returnLevels.size();i++){
for(int j =0;j<returnLevels.get(i).size();j++){
System.out.print(returnLevels.get(i).get(j)+" ");
}
System.out.println();
}
System.out.println("Hello World!");
}
static List<List<Integer>> levels = new ArrayList<>();
static List<List<Integer>> returnLevels = new ArrayList<>();
public static List<List<Integer>> levelOrderBottom(TreeNode root) {
if (root == null){
return levels;
}
helper(root, 0);
for (int i = levels.size()-1; i >=0 ; i--) {
returnLevels.add(levels.get(i));
}
return returnLevels;
}
private static void helper(TreeNode node, int level) {
// start the current level
if (levels.size() == level) {
levels.add(new ArrayList<>());
}
levels.get(level).add(node.val);
if (node.left != null) {
helper(node.left, level + 1);
}
if (node.right != null){
helper(node.right, level + 1);
}
}
}
bfs
public List<List<Integer>> levelOrderBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> ans = new LinkedList<List<Integer>>();
if (root == null)
return ans;
queue.offer(root);
while (!queue.isEmpty()) {
int levelNum = queue.size(); // 当前层元素的个数
List<Integer> subList = new LinkedList<Integer>();
for (int i = 0; i < levelNum; i++) {
TreeNode curNode = queue.poll();
if (curNode != null) {
subList.add(curNode.val);
queue.offer(curNode.left);
queue.offer(curNode.right);
}
}
if (subList.size() > 0) {
ans.add(0, subList);
}
}
return ans;
}
京公网安备 11010502036488号