給定一個(gè)二叉樹(shù)赛糟，返回其節(jié)點(diǎn)值的鋸齒形層序遍歷淤刃。（即先從左往右睁搭，再?gòu)挠彝筮M(jìn)行下一層遍歷赶诊，以此類(lèi)推，層與層之間交替進(jìn)行）
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
示例1：
給定二叉樹(shù) [3,9,20,null,null,15,7],
3/
9 20
/
15 7
返回鋸齒形層序遍歷如下：[
[3],
[20,9],
[15,7]
]
Java解法
思路：
- 昨天用棧實(shí)現(xiàn)時(shí)就導(dǎo)致了這種現(xiàn)象
- 放入取出再放入正好帶來(lái)了這種效果
package sj.shimmer.algorithm.m3_2021;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import sj.shimmer.algorithm.TreeNode;
/**
* Created by SJ on 2021/3/19.
*/
class D53 {
public static void main(String[] args) {
System.out.println(zigzagLevelOrder(TreeNode.getInstance(new Integer[]{3, 9, 20, null, null, 15, 7})));
System.out.println(zigzagLevelOrder(TreeNode.getInstance(new Integer[]{1,2,3,4,5})));
}
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root != null) {
stack.add(root);
}
boolean toRight = true;
while (!stack.isEmpty()){
List<Integer> tempList = new ArrayList<>();
Stack<TreeNode> temp = new Stack<>();
while (!stack.isEmpty()) {
TreeNode pop = stack.pop();
if (pop != null) {
tempList.add(pop.val);
if (toRight) {
temp.add(pop.left);
temp.add(pop.right);
}else {
temp.add(pop.right);
temp.add(pop.left);
}
}
}
toRight=!toRight;
if (tempList.size()!=0) {
results.add(tempList);
stack = temp;
}
}
return results;
}
}
image
官方解
-
廣度優(yōu)先遍歷
使用隊(duì)列處理园骆，大致邏輯差不多
時(shí)間復(fù)雜度：O(N)
空間復(fù)雜度：O(N)
