【数据结构与算法】【LeetCode】【二叉树】103.二叉树的锯齿形层序遍历

fishni

数据结构与算法

发布于：2020年11月30日

迭代：广度优先遍历，递归：深度优先遍历

题目

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

例如：

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

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

[
  [3],
  [20,9],
  [15,7]
]

题解

方法一：BFS（广度优先遍历）

思路

最直接BFS，逐层遍历

BFS 在每层的默认顺序是从左到右，因此需要调整 BFS 算法以生成锯齿序列

最关键的是使用双端队列遍历，可以在队列的任一端插入元素。

如果需要 FIFO （先进先出）的顺序，则将新元素添加到队列尾部，后插入的元素就可以排在后面。

如果需要 FILO （先进后出）的顺序，则将新元素添加到队列首部，后插入的元素就可以排在前面。

算法

实现 BFS 的几种算法。

使用两层嵌套循环。外层循环迭代树的层级，内层循环迭代每层上的节点。

也可以使用一层循环实现 BFS。将要访问的节点添加到队列中，使用分隔符（例如：空节点）把不同层的节点分隔开。分隔符表示一层结束和新一层开始。

这里采用第二种方法。在此算法的基础上，借助双端队列实现锯齿形顺序。在每一层，使用一个空的双端队列保存该层所有的节点。根据每一层的访问顺序，即从左到右或从右到左，决定从双端队列的哪一端插入节点。

实现从左到右的遍历顺序（FIFO）。将元素添加到队列尾部，保证后添加的节点后被访问。从上图中可以看出，输入序列 [1, 2, 3, 4, 5]，按照 FIFO 顺序得到输出序列为 [1, 2, 3, 4, 5]。

实现从右到左的遍历顺序（FILO）。将元素添加到队列头部，保证后添加的节点先被访问。输入序列 [1, 2, 3, 4, 5]，按照 FILO 顺序得到输出序列为 [5, 4, 3, 2, 1]。

from queue import Queue

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
def create_tree(list_tree):
    if  not list_tree:
        return []
    new_queue= Queue()
    root = TreeNode(list_tree[0])
    new_queue.put(root) # 先入队一个结点
    count = 1
    while not new_queue.empty() and count<len(list_tree):
        dequeue = new_queue.get() # 出队
        if not dequeue.left and  not dequeue.right:
            if count<len(list_tree) and list_tree[count]:
                dequeue.left=TreeNode(list_tree[count])
            count= count+1
            if count<len(list_tree) and list_tree[count]:
                dequeue.right=TreeNode(list_tree[count])
            count= count+1

            if dequeue.left:
                new_queue.put(dequeue.left)
            if dequeue.right:
                new_queue.put(dequeue.right)
    return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque

class Solution:
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        ret = []
        level_list = deque()
        if root is None:
            return []
        # start with the level 0 with a delimiter
        node_queue = deque([root, None])
        is_order_left = True

        while len(node_queue) > 0:
            curr_node = node_queue.popleft()

            if curr_node:
                if is_order_left:
                    level_list.append(curr_node.val)
                else:
                    level_list.appendleft(curr_node.val)

                if curr_node.left:
                    node_queue.append(curr_node.left)
                if curr_node.right:
                    node_queue.append(curr_node.right)
            else:
                # we finish one level
                ret.append(level_list)
                # add a delimiter to mark the level
                if len(node_queue) > 0:
                    node_queue.append(None)

                # prepare for the next level
                level_list = deque()
                is_order_left = not is_order_left

        return ret
root =  [3,9,20,None,None,15,7]
root_tree=create_tree(root)
a=Solution()
result =a.zigzagLevelOrder(root_tree)
result

[deque([3]), deque([20, 9]), deque([15, 7])]

注意：一种替代做法是，实现标准的 BFS 算法，得到每层节点从左到右的遍历顺序。然后按照要求翻转某些层节点的顺序，得到锯齿形的遍历结果。

方法二：DFS （深度优先遍历）

思路

也可以使用 DFS 实现 BFS 的遍历顺序。

在 DFS 遍历期间，将结果保存在按层数索引的全局数组中。即元素 array[level] 存储同一层的所有节点。然后在 DFS 的每一步更新全局数组

与改进的 BFS 算法类似，使用双端队列保存同一层的所有节点，并交替插入方向（从首部插入或从尾部插入）得到需要的输出顺序。

算法

使用递归实现 DFS 算法。定义一个递归方法 DFS(node, level)，方法参数为当前节点 node 和指定层数 level。该方法共执行三个步骤：

如果是第一次访问该层的节点，即该层的双端队列不存在。那么创建一个双端队列，并添加该节点到队列中。
如果当前层的双端队列已存在，根据顺序，将当前节点插入队列头部或尾部。
最后，为每个节点调用该递归方法。

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []

        results = []
        def dfs(node, level):
            if level >= len(results):
                results.append(deque([node.val]))
            else:
                if level % 2 == 0:
                    results[level].append(node.val)
                else:
                    results[level].appendleft(node.val)

            for next_node in [node.left, node.right]:
                if next_node is not None:
                    dfs(next_node, level+1)

        # normal level order traversal with DFS
        dfs(root, 0)

        return results
    
root =  [3,9,20,None,None,15,7,6]
root_tree=create_tree(root)
a=Solution()
result =a.zigzagLevelOrder(root_tree)
result

[deque([3]), deque([20, 9]), deque([15, 7]), deque([6])]

【数据结构与算法】【LeetCode】【二叉树】98.验证二叉搜索树

递归、深度优先遍历题目给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有...

【数据结构与算法】【LeetCode】【二叉树】102.二叉树的层序遍历

迭代：广度优先遍历，递归：深度优先遍历题目给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。示例：二叉树：[3,9,20,null,null,1...