算法题--分层按ZIGZAG路线收集二叉树中的元素

image.png

0. 链接

题目链接

1. 题目

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

2. 思路1: 递归实现

• 定义遍历方法，带有参数node, level, from_left, results
• 将node收集到results[level-1]中去之后, 继续递归收集下一层的节点node.left, node.right 且level+1, not from_left

3. 代码

# coding:utf8
from typing import List


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


class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:

        def traversal(results, node, level=1, from_left=True):
            if node is None:
                return
            if len(results) < level:
                results.append(list())
            if from_left:
                results[level - 1].append(node.val)
            else:
                results[level - 1].insert(0, node.val)
            traversal(results, node.left, level + 1, not from_left)
            traversal(results, node.right, level + 1, not from_left)

        results = list()
        traversal(results, root)

        return results


solution = Solution()

root1 = node = TreeNode(3)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)

print(solution.zigzagLevelOrder(root1))

输出结果

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

4. 结果

image.png