剑指offer-python

把二叉树打印成多层[层次搜索]、以及之字形打印

2018-08-28  本文已影响0人  小歪与大白兔

题目一:
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        #广度优先搜索(层次搜索)
        #用栈可以简单实现
        if pRoot is None:
            return []
        result = []#存储最终的输出结果
        currentstack = [pRoot] # 存储当前层入栈的节点
        while currentstack:
            res = []  #存储该层的结果
            nextstack = []  #存储下一层入栈的节点
            for i in currentstack:
                res.append(i.val)
                if i.left:
                    nextstack.append(i.left)
                if i.right:
                    nextstack.append(i.right)
            currentstack = nextstack
            result.append(res)
        return result

题目二:
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
思路:只需在上一题中新增一个time用来记录当前是奇数层还是偶数层即可;如果是偶数层,则将res中的元素反转:res.reverse()或者是res = res[::-1]

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        #广度优先搜索(层次搜索)
        #用栈可以简单实现
        if pRoot is None:
            return []
        result = []#存储最终的输出结果
        currentstack = [pRoot] # 存储当前层入栈的节点
        time = 0
        while currentstack:
            res = []  #存储该层的结果
            nextstack = []  #存储下一层入栈的节点
            time += 1
            for i in currentstack:
                res.append(i.val)
                if i.left:
                    nextstack.append(i.left)
                if i.right:
                    nextstack.append(i.right)
            currentstack = nextstack
            if time % 2== 0:
                res.reverse()
            result.append(res)
        return result
上一篇 下一篇

猜你喜欢

热点阅读