剑指offer:从上到下打印二叉树-创新互联
题目描述
从上往下打印出二叉树的每个节点,同层节点从左至右打印。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
"""
由于需要逐层打印,那么我们在遍历整棵树的时候就需要维护一个队列。
队列中存储的是下一层从左到右的节点。
具体来说在打印第k层的节点的时候,将该节点的左右子节点按顺序入队即可。递归出口就是队列为空
"""
def PrintFromTopToBottom(self, root):
def helper(root_queue, ans):
# 递归出口即队列为空
if not root_queue:
return
length = len(root_queue)
for i in range(length):
# 对于某个节点,在打印完它的值之后,将其左右子节点先后入队
ans.append(root_queue[i].val)
if root_queue[i].left:
root_queue.append(root_queue[i].left)
if root_queue[i].right:
root_queue.append(root_queue[i].right)
helper(root_queue[length:], ans)
res = []
if not root:
return res
helper([root], res)
return res
def main():
root = TreeNode(8)
root.left = TreeNode(6)
root.right = TreeNode(10)
root.left.left = TreeNode(5)
root.left.right = TreeNode(7)
root.right.left = TreeNode(9)
root.right.right = TreeNode(11)
solution = Solution()
print(solution.PrintFromTopToBottom(root))
if __name__ == '__main__':
main()
另外有需要云服务器可以了解下创新互联cdcxhl.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
新闻名称:剑指offer:从上到下打印二叉树-创新互联
URL网址:http://scyanting.com/article/csseci.html