锯齿形水平顺序遍历

Question

I am trying to do the zigzag level order traversal of a binary tree's nodes values (ie, from left to right, then right to left for the next level and alternate between) on https://www.interviewbit.com/problems/zigzag-level-order-traversal-bt/ But the compiler gives time limit exceeded error. How can I resolve it?

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

class Solution:
    # @param A : root node of tree
    # @return a list of list of integers
    def zigzagLevelOrder(self, A):
        st_crt_lvl =[A]
        st_nxt_lvl =[]
        ans_list = []

        while st_crt_lvl:
            u = st_crt_lvl.pop(0)
            ans_list.append(u.val) 
            if u.left:
                st_nxt_lvl.append(u.left)
            if u.right:
                st_nxt_lvl.append(u.right)
            while st_nxt_lvl:
                u = st_nxt_lvl.pop()
                ans_list.append(u.val)

                if u.right:
                    st_crt_lvl.append(u.right)
                if u.left:
                    st_crt_lvl.append(u.left)


        return ans_list

Answer 1

您可以从代码中消除多个内部while循环，方法是使队列st_nxt_lvl临时，并在二叉树的每个级别的处理结束时将此临时队列的内容复制到当前队列{}。在

这可以通过保持一个队列（没有任何临时存储）和标准bfs算法进行级别顺序遍历来实现，但是由于我们希望在每个级别上进行锯齿形顺序遍历，所以有一个临时队列更为优雅，因此临时队列只保留下一级元素，当处理完当前级别元素时，当前队列指向下一级。在

通过对代码进行一些修改，以及一个示例树：

def zigzagLevelOrder(A):

    st_crt_lvl = [A] # initialize
    ans_list = []   

    level = 0
    while st_crt_lvl: # check if all levels are processed
        st_nxt_lvl =[] # temporary queue to hold the next level elements
        tmp = [] # temporary storage to append to the ans_list 
        while st_crt_lvl:
            u = st_crt_lvl.pop(0)
            tmp.append(u.val) 
            if u.left:
                st_nxt_lvl.append(u.left)
            if u.right:
                st_nxt_lvl.append(u.right)                
        if (len(tmp) > 0): # if tmp is not empty
            if level % 2 == 1: # ensure zig-zag level order traversal
                tmp = tmp[::-1]
            ans_list.append(tmp)
        st_crt_lvl = st_nxt_lvl  # copy the temporary queue to the current queue      
        level += 1

    return ans_list


class BinaryTree:
    def __init__(self, left, right, data):
        self.left = left
        self.right = right
        self.val = data

A = BinaryTree(None, None, 3)
A.left = BinaryTree(None, None, 9)
A.right = BinaryTree(None, None, 20)
A.left.left = BinaryTree(None, None, 1)
A.left.right = BinaryTree(None, None, 2)
A.right.left = BinaryTree(None, None, 15)
A.right.right = BinaryTree(None, None, 7)
zigzagLevelOrder(A)
# [[3], [20, 9], [1, 2, 15, 7]]

Answer 2

您可以使用宽度优先搜索：

from collections import deque, defaultdict
class Tree:
  def __init__(self, **kwargs):
    self.__dict__ = {i:kwargs.get(i) for i in ['left', 'right', 'value']}
  def __contains__(self, _val):
   if self.value != _val and self.left is None and self.right is None:
     return False
   return True if self.value == _val else any([_val in [[], self.left][self.left is not None], _val in [[], self.right][self.right is not None]])
  def __lookup(self, _val, _depth = 0):
    if self.value == _val:
      return _depth
    return getattr(self, 'left' if _val in self.left else 'right').__lookup(_val, _depth+1)
  def __getitem__(self, _val):
    return self.__lookup(_val)    

def bfs(_head):
  _d = deque([_head])
  _seen = []
  _last = None
  _final_result = defaultdict(list)
  while _d:
   _current = _d.popleft()
   if _current.value not in _seen:
      _seen.append(_current.value)
      _r = list(filter(None, [getattr(_current, i, None) for i in ['left', 'right']]))
      _d.extend(_r)
      _final_result[_head[_current.value]].append(_current.value)
  marker = iter(range(len(_final_result)))
  return [i[::-1] if next(marker)%2 else i for _, i in sorted(_final_result.items(), key=lambda x:x[0])]

---

当从问题中的链接构造示例中的同一棵树时，输出为：

^{pr2}$

输出：

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

此解决方案使用breadth-first search水平遍历树。但是，由于（完整的）二叉树有两个子级，因此只有两个值将添加到队列中。因此，为了确定搜索已达到的当前树级别，必须在树（__getitem__和__lookup）中实现查找特定值深度的方法。在