S2
S2 copied to clipboard
halfrost
0103. Binary Tree Zigzag Level Order Traversal | LeetCode Cookbook
https://books.halfrost.com/leetcode/ChapterFour/0100~0199/0103.Binary-Tree-Zigzag-Level-Order-Traversal/
func zigzagLevelOrder(root *TreeNode) [][]int {
var res [][]int
search(root, 0, &res)
return res
}
func search(root *TreeNode, depth int, res *[][]int) {
if root == nil {
return
}
for len(*res) < depth+1 {
*res = append(*res, []int{})
}
if depth%2==0 {
(*res)[depth] = append((*res)[depth], root.Val)
}else{
(*res)[depth] = append([]int{root.Val}, (*res)[depth]...)
}
search(root.Left, depth+1, res)
search(root.Right, depth+1, res)
}
@techkang
func zigzagLevelOrder(root *TreeNode) [][]int { var res [][]int search(root, 0, &res) return res } func search(root *TreeNode, depth int, res *[][]int) { if root == nil { return } for len(*res) < depth+1 { *res = append(*res, []int{}) } if depth%2==0 { (*res)[depth] = append((*res)[depth], root.Val) }else{ (*res)[depth] = append([]int{root.Val}, (*res)[depth]...) } search(root.Left, depth+1, res) search(root.Right, depth+1, res) }
@techkang 我之前也用你这个解法提交过，当时内存比现在这个解法略高一些，我就写了现在这个了。不过现在看来，递归的解法也挺简洁的。我也放进题解吧。谢谢你~❤️
说个简单点的想法 迭代的方式 用队列写层序遍历, 设置个flag 每次层序遍历若flag==true 该层不逆序 ,把flag改为false 若flag==false,该层逆序,flag改为true JAVA代码
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
Queue<TreeNode> queue = new LinkedList();
List<List<Integer>> ans = new ArrayList<>();
queue.add(root);
boolean flag = true;
while (!queue.isEmpty()) {
int len = queue.size();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < len; i++) {
TreeNode cur = queue.poll();
list.add(cur.val);
if (cur.left != null)
queue.add(cur.left);
if (cur.right != null)
queue.add(cur.right);
}
if (flag) {
flag = false;
} else {
Collections.reverse(list);
flag = true;
}
ans.add(list);
}
return ans;
}
}
}
说个简单点的想法 迭代的方式 用队列写层序遍历, 设置个flag 每次层序遍历若flag==true 该层不逆序 ,把flag改为false 若flag==false,该层逆序,flag改为true JAVA代码
class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { if (root == null) return new ArrayList<>(); Queue<TreeNode> queue = new LinkedList(); List<List<Integer>> ans = new ArrayList<>(); queue.add(root); boolean flag = true; while (!queue.isEmpty()) { int len = queue.size(); List<Integer> list = new ArrayList<>(); for (int i = 0; i < len; i++) { TreeNode cur = queue.poll(); list.add(cur.val); if (cur.left != null) queue.add(cur.left); if (cur.right != null) queue.add(cur.right); } if (flag) { flag = false; } else { Collections.reverse(list); flag = true; } ans.add(list); } return ans; } } }
@OpensourceHU 你这个解法挺简洁的，思路很清晰👍🏻
func zigzagLevelOrder(root *TreeNode) [][]int {
res := [][]int{}
if root == nil{
return res
}
q := []*TreeNode{root}
var size, i, j int
var lay []int
var tmp []*TreeNode
var flag bool
flag = false
for len(q) > 0{
size = len(q)
tmp = []*TreeNode{}
lay = make([]int, size)
j = size-1
for i=0; i<size; i++{
root = q[0]
q = q[1:]
if !flag{
lay[i] = root.Val
}else{
lay[j] = root.Val
j--
}
if root.Left != nil{
tmp = append(tmp, root.Left)
}
if root.Right != nil{
tmp = append(tmp, root.Right)
}
}
res = append(res, lay)
flag = !flag
q = tmp
}
return res
}
@crissu func zigzagLevelOrder(root *TreeNode) [][]int { res := [][]int{} if root == nil{ return res } q := []*TreeNode{root} var size, i, j int var lay []int var tmp []*TreeNode var flag bool flag = false for len(q) > 0{ size = len(q) tmp = []*TreeNode{} lay = make([]int, size) j = size-1 for i=0; i<size; i++{ root = q[0] q = q[1:] if !flag{ lay[i] = root.Val }else{ lay[j] = root.Val j-- } if root.Left != nil{ tmp = append(tmp, root.Left) } if root.Right != nil{ tmp = append(tmp, root.Right) }
} res = append(res, lay) flag = !flag q = tmp } return res }
BFS 的解法也很好。想提交一个 PR 把你的解法也合并进题解不？😉
@crissu func zigzagLevelOrder(root *TreeNode) [][]int { res := [][]int{} if root == nil{ return res } q := []*TreeNode{root} var size, i, j int var lay []int var tmp []*TreeNode var flag bool flag = false for len(q) > 0{ size = len(q) tmp = []*TreeNode{} lay = make([]int, size) j = size-1 for i=0; i<size; i++{ root = q[0] q = q[1:] if !flag{ lay[i] = root.Val }else{ lay[j] = root.Val j-- } if root.Left != nil{ tmp = append(tmp, root.Left) } if root.Right != nil{ tmp = append(tmp, root.Right) }
} res = append(res, lay) flag = !flag q = tmp } return res }BFS 的解法也很好。想提交一个 PR 把你的解法也合并进题解不？😉
可以的
可以BFS直接套用102题的代码，改一下每层加入返回值数组的节点顺序即可，用了滚动数组时间也是beat 100%的:
func zigzagLevelOrder(root *TreeNode) (res [][]int) {
if root == nil {
return
}
levels := [2][]*TreeNode{}
levels[0] = []*TreeNode{root}
for len(levels[len(res)%2]) != 0 {
curr := len(res) % 2
next := (curr + 1) % 2
levels[next] = nil
res = append(res, nil)
for i, node := range levels[curr] {
if curr % 2 == 0 {
res[len(res)-1] = append(res[len(res)-1], node.Val)
} else {
res[len(res)-1] = append(res[len(res)-1], levels[curr][len(levels[curr])-1-i].Val)
}
if node.Left != nil {
levels[next] = append(levels[next], node.Left)
}
if node.Right != nil {
levels[next] = append(levels[next], node.Right)
}
}
}
return
}
套用层序遍历 func zigzagLevelOrder(root *TreeNode) [][]int { queue := []*TreeNode{root} res := [][]int{} if root == nil { return res } flag := true //true 表示从左向右遍历 for len(queue) != 0 { n := len(queue) temp := make([]int,n) for i :=0;i<n;i++{ if queue[i].Left != nil { queue = append(queue,queue[i].Left) } if queue[i].Right != nil { queue = append(queue,queue[i].Right) } if flag { temp[i] = queue[i].Val }else { temp[i] = queue[n-i-1].Val } }
queue = queue[n:]
flag =!flag
res = append(res,temp)
}
return res }
