首页 > 代码库 > Leetcode 103. Binary Tree Zigzag Level Order Traversal

Leetcode 103. Binary Tree Zigzag Level Order Traversal

2024-09-02 08:34:45   214人阅读

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]
]

思路类似： level order Traversal，唯一的区别在于对于第一层，Push child进入stack的顺序是left then right。而第二层是right then left。用一个boolean dicrect 来控制这个方向，每一层取反一次。

技术分享

 

 1 class Solution(object):
 2     def zigzagLevelOrder(self, root):
 3         """
 4         :type root: TreeNode
 5         :rtype: List[List[int]]
 6         """
 7         stack1 = []
 8         stack2 = []
 9         stack1.append(root)
10         direct = True
11         ans = []
12         while stack1:
13             self.helper(direct, ans, stack1, stack2)
14             stack1, stack2 = stack2, []
15             direct = not direct
16         return ans[:-1]
17     
18     
19     def helper(self, direct, ans, stack1, stack2):
20         line = []
21         while stack1:
22             cur = stack1.pop()
23             if cur != None:
24                 line.append(cur.val)                
25                 if direct == True:
26                     stack2.append(cur.left)
27                     stack2.append(cur.right)
28                 else:
29                     stack2.append(cur.right)
30                     stack2.append(cur.left)
31         ans.append(line)

 

Leetcode 103. Binary Tree Zigzag Level Order Traversal


联系
我们