算法题--分层按ZIGZAG路线收集二叉树中的元素
2020-04-28 本文已影响0人
岁月如歌2020
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]]