LeetCode-103-二叉树的锯齿形层序遍历
103. 二叉树的锯齿形层序遍历
难度中等450收藏分享切换为英文接收动态反馈
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下：
[
[3],
[20,9],
[15,7]
]
class Solution {
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
LinkedList<TreeNode> deque = new LinkedList<>();
deque.add(root);
int size = 0;
boolean isHead = true;
while (!deque.isEmpty()) {
size = deque.size();
List<Integer> curLevel = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode cur = isHead ? deque.pollFirst() : deque.pollLast();
curLevel.add(cur.val);
if(isHead) {
if (cur.left != null) {
deque.addLast(cur.left);
}
if (cur.right != null) {
deque.addLast(cur.right);
}
}else {
if (cur.right != null) {
deque.addFirst(cur.right);
}
if (cur.left != null) {
deque.addFirst(cur.left);
}
}
}
ans.add(curLevel);
isHead = !isHead;
}
return ans;
}
}
image-20210606142704542
递归写法
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if(root == null) return res;
helper(root, 0, true);
return res;
}
private void helper(TreeNode root, int level, boolean left){
if(root == null) return;
if(level >= res.size()) res.add(new ArrayList<Integer>());
if(left) res.get(level).add(root.val);
if(!left) res.get(level).add(0,root.val);
helper(root.left, level+1, !left);
helper(root.right, level+1, !left);
}
}
image-20210606142858017
