103. Binary Tree Zigzag Level Order Traversal

Kesa...大约 4 分钟

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
img
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100

1. 广度优先遍历

1.1 单队列

func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}

    if root == nil {
        return res
    }

    // Queue
    q := []*TreeNode{root}
    cnt := 1 // 当前层节点数
    next := 0 // 下一层节点数
    vals := []int{}

    for lvl := 0; len(q) > 0; {
        cur := q[0]
        q = q[1:]
        cnt--
        vals = append(vals, cur.Val)

        if cur.Left != nil {
            q = append(q, cur.Left)
            next++
        } 
        if cur.Right != nil {
            q = append(q, cur.Right)
            next++
        }

        // 当前层结束
        if cnt == 0 {
            // 奇数层反转
            if lvl % 2 == 1 {
                reverse(vals)
            }
            res = append(res, vals)

            vals = []int{}
            cnt = next 
            next = 0
            lvl++
        }
    }

    return res
}

func reverse(s []int) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

1.2 双队列

func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}

    if root == nil {
        return res
    }

    // Queue
    q1 := []*TreeNode{root}
    q2 := []*TreeNode{}
    vals := []int{}

    for lvl := 0; len(q1) > 0; {
        cur := q1[0]
        q1 = q1[1:]
        vals = append(vals, cur.Val)

        if cur.Left != nil {
            q2 = append(q2, cur.Left)
        }
        if cur.Right != nil {
            q2 = append(q2, cur.Right)
        }

        if len(q1) == 0 {
            if lvl % 2 == 1 {
                reverse(vals)
            }
            res = append(res, vals)

            q1, q2 = q2, q1
            vals = []int{}
            lvl++
        }
    }

    return res
}

func reverse(s []int) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

2. 深度优先遍历

2.1 递归

Preorder

func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    dfsPreorder(root, 0, &res)
    return res
}

func dfsPreorder(root *TreeNode, depth int, res *[][]int) {
    if root == nil {
        return 
    }

    if len(*res) < depth+1 {
        *res = append(*res, []int{})
    }

    // Odd level
    if depth & 1 == 1 {
        (*res)[depth] = prepend(root.Val, (*res)[depth])
    } else {
        (*res)[depth] = append((*res)[depth], root.Val)
    }

    dfsPreorder(root.Left, depth+1, res)

    dfsPreorder(root.Right, depth+1, res)
}

func prepend(x int, a []int) []int {
    a = append(a, 0)
    copy(a[1:], a)
    a[0] = x
    return a
}

Inorder

func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    dfsInorder(root, 0, &res)
    return res
}

func dfsInorder(root *TreeNode, depth int, res *[][]int) {
    if root == nil {
        return 
    }

    if len(*res) < depth+1 {
        *res = append(*res, []int{})
    }

    dfsInorder(root.Left, depth+1, res)

    // Odd level
    if depth & 1 == 1 {
        (*res)[depth] = prepend(root.Val, (*res)[depth])
    } else {
        (*res)[depth] = append((*res)[depth], root.Val)
    }

    dfsInorder(root.Right, depth+1, res)
}

func prepend(x int, a []int) []int {
    a = append(a, 0)
    copy(a[1:], a)
    a[0] = x
    return a
}

Postorder

func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    dfsPostorder(root, 0, &res)
    return res
}

func dfsPostorder(root *TreeNode, depth int, res *[][]int) {
    if root == nil {
        return 
    }

    if len(*res) < depth+1 {
        *res = append(*res, []int{})
    }

    dfsPostorder(root.Left, depth+1, res)

    dfsPostorder(root.Right, depth+1, res)

    // Odd level
    if depth & 1 == 1 {
        (*res)[depth] = prepend(root.Val, (*res)[depth])
    } else {
        (*res)[depth] = append((*res)[depth], root.Val)
    }
}

func prepend(x int, a []int) []int {
    a = append(a, 0)
    copy(a[1:], a)
    a[0] = x
    return a
}

2.2 迭代+栈

前序

func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    // Stack
    st := []NodeWithDepth{}
    cur := NodeWithDepth{Node: root, Depth: 0}

    // Preorder
    for cur.Node != nil || len(st) > 0 {
        for cur.Node != nil {
            if len(res) < cur.Depth+1 {
                res = append(res, []int{})
            }
            // odd level
            if cur.Depth & 1 == 1 {
                res[cur.Depth] = prepend(cur.Node.Val, res[cur.Depth])
            } else {
                res[cur.Depth] = append(res[cur.Depth], cur.Node.Val)
            }

            st = append(st, cur)
            cur = NodeWithDepth{Node: cur.Node.Left, Depth: cur.Depth+1}
        }

        cur, st = st[len(st)-1], st[:len(st)-1]
        
        cur = NodeWithDepth{Node: cur.Node.Right, Depth: cur.Depth+1}
    }

    return res
}

func prepend(x int, a []int) []int {
    a = append(a, 0)
    copy(a[1:], a)
    a[0] = x
    return a
}

type NodeWithDepth struct {
    Node *TreeNode
    Depth int
}

中序

func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    // Stack
    st := []NodeWithDepth{}
    cur := NodeWithDepth{Node: root, Depth: 0}

    // Preorder
    for cur.Node != nil || len(st) > 0 {
        for cur.Node != nil {
            if len(res) < cur.Depth+1 {
                res = append(res, []int{})
            }

            st = append(st, cur)
            cur = NodeWithDepth{Node: cur.Node.Left, Depth: cur.Depth+1}
        }

        cur, st = st[len(st)-1], st[:len(st)-1]
        // odd level
        if cur.Depth & 1 == 1 {
            res[cur.Depth] = prepend(cur.Node.Val, res[cur.Depth])
        } else {
            res[cur.Depth] = append(res[cur.Depth], cur.Node.Val)
        }
        
        cur = NodeWithDepth{Node: cur.Node.Right, Depth: cur.Depth+1}
    }

    return res
}

func prepend(x int, a []int) []int {
    a = append(a, 0)
    copy(a[1:], a)
    a[0] = x
    return a
}

type NodeWithDepth struct {
    Node *TreeNode
    Depth int
}

后序

func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    // Stack
    st := []NodeWithDepth{}
    cur := NodeWithDepth{Node: root, Depth: 0}
    prev := NodeWithDepth{}

    // Preorder
    for cur.Node != nil || len(st) > 0 {
        for cur.Node != nil {
            if len(res) < cur.Depth+1 {
                res = append(res, []int{})
            }

            st = append(st, cur)
            cur = NodeWithDepth{Node: cur.Node.Left, Depth: cur.Depth+1}
        }

        cur = st[len(st)-1]
        if cur.Node.Right != nil && cur.Node.Right != prev.Node {
            cur = NodeWithDepth{Node: cur.Node.Right, Depth: cur.Depth+1}
        } else {
            st = st[:len(st)-1]

            // Odd level 
            if cur.Depth & 1 == 1{
                res[cur.Depth] = prepend(cur.Node.Val, res[cur.Depth])
            } else {
                res[cur.Depth] = append(res[cur.Depth], cur.Node.Val)
            }

            prev = cur
            cur = NodeWithDepth{}
        }
    }

    return res
}

func prepend(x int, a []int) []int {
    a = append(a, 0)
    copy(a[1:], a)
    a[0] = x
    return a
}

type NodeWithDepth struct {
    Node *TreeNode
    Depth int
}

Reference

https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/solutionsopen in new window

昵称

邮箱

网址

按正序
按倒序
按热度

103. Binary Tree Zigzag Level Order Traversal

# 1. 广度优先遍历

# 1.1 单队列

# 1.2 双队列

# 2. 深度优先遍历

# 2.1 递归

# Preorder

# Inorder

# Postorder

# 2.2 迭代+栈

# 前序

# 中序

# 后序

# Reference

预览:

1. 广度优先遍历

1.1 单队列

1.2 双队列

2. 深度优先遍历

2.1 递归

Preorder

Inorder

Postorder

2.2 迭代+栈

前序

中序

后序

Reference