算法:二叉树的啮齿形层序遍历(蛇形遍历)
算法 About 2,145 words示例
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
3
/ \
9 20
/ \
15 7
返回
[
[3],
[20,9],
[15,7]
]
思路
层序遍历时使用深度优先搜索递归方式遍历每一层,第1
层从左往右,第2
层从右往左,以此类推。只要递归传入层数(注意每玩下递归一次都+1
),奇数层从尾部添加,偶数层从头部添加。
private List<List<Integer>> levelList = new ArrayList<>();
public void bfsR(Node root, int level) {
if (root == null) {
return;
}
if (level >= levelList.size()) {
levelList.add(new ArrayList<>());
}
// %2 判断奇偶层
if (level % 2 == 0) {//第奇数层(从1开始计算层高),从头部开始加
levelList.get(level).add(root.id);
} else { // 第偶数层,从尾部开始加
levelList.get(level).add(0, root.id);
}
bfsR(root.left, level + 1);
bfsR(root.right, level + 1);
}
完整代码
public class TreeZigzag {
public static void main(String[] args) {
TreeZigzag tree = new TreeZigzag();
Node node3 = new Node(3);
Node node9 = new Node(9);
Node node20 = new Node(20);
Node node15 = new Node(15);
Node node7 = new Node(7);
node3.left = node9;
node3.right = node20;
node20.left = node15;
node20.right = node7;
tree.root = node3;
tree.bfsR(tree.root, 0);
System.out.println(tree.levelList);
}
public Node root;
private List<List<Integer>> levelList = new ArrayList<>();
public void bfsR(Node root, int level) {
if (root == null) {
return;
}
if (level >= levelList.size()) {
levelList.add(new ArrayList<>());
}
// %2 判断奇偶层
if (level % 2 == 0) {//第奇数层(从1开始计算层高),从头部开始加
levelList.get(level).add(root.id);
} else { // 第偶数层,从尾部开始加
levelList.get(level).add(0, root.id);
}
bfsR(root.left, level + 1);
bfsR(root.right, level + 1);
}
private static class Node {
public int id;
public Node left;
public Node right;
public Node(int id) {
this.id = id;
}
}
}
LeetCode 原题地址
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
Views: 2,052 · Posted: 2021-02-27
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...