【剑指offer】面试题32 - III. 从上到下打印二叉树 III

题目描述

面试题32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

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

分析

1.此题跟上一题相比,只是不同层的访问顺序改变,加了个记录深度的变量,尝试写了下根据深度不同访问顺序不同,结果会影响到后面的子树,即若第二层先右子树后左子树,结果在第三层先访问了第二层中右子树的左子树了,没修改好... 就直接按照上一题解法对每一层的list判断深度决定是否翻转了,行吧,这样也能解决。我再去评论区看看大神们都是怎么写的

解题

1.

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if(not root):
            return []
        res=[]
        temp=[root]
        dep=0
        while(temp):
            dep+=1
            length = len(temp)
            a=[]
            for i in range(length):
                cur=temp.pop(0)
                a.append(cur.val)
                if(cur.left):
                    temp.append(cur.left)
                if(cur.right):
                    temp.append(cur.right)
            if(dep%2 == 0):
                a.reverse()
            res.append(a)
        return(res)

 

上一篇:leetcode557. 反转字符串中的单词 III python,处理字符串的神!


下一篇:存在重复元素III