首页 > 代码库 > LeetCode 103. Binary Tree Zigzag Level Order Traversal
LeetCode 103. Binary Tree Zigzag Level Order Traversal
原题
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判断是否正序或逆序
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = None# 利用栈迭代class Solution(object): def zigzagLevelOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if root == None: return [] stack, ret = [root], [] dep = 0 while stack: level_value = http://www.mamicode.com/[]>
方法二
- 利用双向队列求解，解题思路跟方法一类似
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = None # 利用双向队列 # Your runtime beats 90.20 % of python submissions.class Solution(object): def zigzagLevelOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if root == None: return [] DQ = collections.deque() DQ.append(root) ret = [] flag = True while DQ: length = len(DQ) level_value = http://www.mamicode.com/[]>
LeetCode 103. Binary Tree Zigzag Level Order Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。