[Leetcode][python]Binary Tree Zigzag Level Order Traversal

拼搏现实的明天。 2022-06-12 09:45 126阅读 0赞

## 题目大意 ##

按之字形遍历二叉树（一正一反）

## 解题思路 ##

来自：[链接][Link 1]  
解题思路：这道题和上一题[层序遍历][Link 2]那道题差不多，区别只是在于奇数层的节点要翻转过来存入数组。  
代码：

## 代码 ##

### BFS ###

class Solution(object):
        def zigzagLevelOrder(self, root):
            tree = []
            if not root:
                return tree
            curr_level = [root]
            direction = 'L'
            # print(type(root), type(curr_level))  # (<class 'precompiled.treenode.TreeNode'>, <type 'list'>)
            # print(curr_level)  # 作为list，却并不能遍历整个树
            while curr_level:
                level_list = []
                next_level = []
                for temp in curr_level:
                    level_list.append(temp.val)
                    if temp.left:
                        next_level.append(temp.left)
                    if temp.right:
                        next_level.append(temp.right)
                if direction == 'L':
                    tree.append(level_list)
                    direction = 'R'
                else:
                    tree.append(level_list[::-1])
                    direction = 'L'
                curr_level = next_level
            return tree

### DFS ###

# Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param root, a tree node
        # @return a list of lists of integers
        def preorder(self, root, level, res):
            if root:
                if len(res) < level+1: res.append([])
                if level % 2 == 0: res[level].append(root.val)
                else: res[level].insert(0, root.val) # 向0位置插入
                self.preorder(root.left, level+1, res)
                self.preorder(root.right, level+1, res)
        def zigzagLevelOrder(self, root):
            res=[]
            self.preorder(root, 0, res)
            return res

## 总结 ##

1.  insert()方法语法：  
    list.insert(index, obj)  
    参数  
    index – 对象 obj 需要插入的索引位置。  
    obj – 要插入列表中的对象。
2.  tree.append(level\_list\[::-1\])将数组倒序插入

[Link 1]: http://www.cnblogs.com/zuoyuan/p/3722004.html
[Link 2]: http://blog.csdn.net/qqxx6661/article/details/75453452