高频算法面试题（四十五）- 二叉树的锯齿形层序遍历

发表于

「这是我参与11月更文挑战的第 30 天，活动详情查看：2021最后一次更文挑战」

刷算法题，从来不是为了记题，而是练习把实际的问题抽象成具体的数据结构或算法模型，然后利用对应的数据结构或算法模型来进行解题。个人觉得，带着这种思维刷题，不仅能解决面试问题，也能更多的学会在日常工作中思考，如何将实际的场景抽象成相应的算法模型，从而提高代码的质量和性能

二叉树的锯齿形层序遍历

题目来源：LeetCode-103. 二叉树的锯齿形层序遍历

题目描述

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）

示例

示例 1

给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
markdown复制代码    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层序遍历如下：

1
2
3
4
5
csharp复制代码[
  [3],
  [20,9],
  [15,7]
]

解题

解法一：广度优先搜索

思路

本题本质上就是二叉树的层序遍历。因此，不难想到用广度优先搜索的思想，实现过程中需要借助一个队列来记录每一层的结点

与层序遍历不同的是，每一层的结果按照锯齿形打印。所以，我们可以偶数层的数据，从左往右打印，奇数层的数据从右往左打印

这道题和高频算法面试题（十九）- 按之字形顺序打印二叉树这道题几乎一样，里边有图解整个过程

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
go复制代码func zigzagLevelOrder(root *TreeNode) (ans [][]int) {
    if root == nil {
        return
    }
    queue := []*TreeNode{root}
    for level := 0; len(queue) > 0; level++ {
        vals := []int{}
        q := queue
        queue = nil
        for _, node := range q {
            vals = append(vals, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        // 本质上和层序遍历一样，我们只需要把奇数层的元素翻转即可
        if level%2 == 1 {
            for i, n := 0, len(vals); i < n/2; i++ {
                vals[i], vals[n-1-i] = vals[n-1-i], vals[i]
            }
        }
        ans = append(ans, vals)
    }
    return
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%