劍指offer：從上到下打印二叉樹(shù)

題目描述

從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。

結(jié)果：[8,6,10,5,7,9,11]

解題思路

典型的使用隊(duì)列的題目。每從隊(duì)列頭部獲取一個(gè)節(jié)點(diǎn)，就將該節(jié)點(diǎn)的左右子節(jié)點(diǎn)存入隊(duì)列的尾部。如此往復(fù)，直至隊(duì)列為空。?

代碼

            
              #coding:utf-8
class Solution:
   #從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印
    def PrintFromTopToBottom(self, root):
        array = []
        result = []
        if root == None:
            return result

        array.append(root)
        while array:
            newNode = array.pop(0)
            result.append(newNode.val)
            if newNode.left != None:  
                array.append(newNode.left)
            if newNode.right != None:
                array.append(newNode.right)
        return result

    # 給定二叉樹(shù)的前序遍歷和中序遍歷，獲得該二叉樹(shù)
    def getBSTwithPreTin(self, pre, tin):
        if len(pre)==0 | len(tin)==0:
            return None

        root = treeNode(pre[0])
        for order,item in enumerate(tin):
            if root .val == item:
                root.left = self.getBSTwithPreTin(pre[1:order+1], tin[:order])
                root.right = self.getBSTwithPreTin(pre[order+1:], tin[order+1:])
                return root

class treeNode:
    def __init__(self, x):
        self.left = None
        self.right = None
        self.val = x

if __name__ == '__main__':
    flag = "printTreeNode"
    solution = Solution()
    preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]
    middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]
    treeRoot1 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq)
    if flag == "printTreeNode":
        newArray = solution.PrintFromTopToBottom(treeRoot1)
        print(newArray)
            
          

leetcode---102.?Binary Tree Level Order Traversal

            
              #coding:utf-8

class Solution:
   #從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印
    def levelOrder(self, root):
        array = []
        result = []
        if root == None:
            return result
        array.append(root)
        while array:
            templist = []
            for i in range(len(array)):
                newNode = array.pop(0)
                templist.append(newNode.val)
                if newNode.left != None:
                    array.append(newNode.left)
                if newNode.right != None:
                    array.append(newNode.right)
            result.append(templist)
        return result

    # 給定二叉樹(shù)的前序遍歷和中序遍歷，獲得該二叉樹(shù)
    def getBSTwithPreTin(self, pre, tin):
        if len(pre)==0 | len(tin)==0:
            return None

        root = treeNode(pre[0])
        for order,item in enumerate(tin):
            if root .val == item:
                root.left = self.getBSTwithPreTin(pre[1:order+1], tin[:order])
                root.right = self.getBSTwithPreTin(pre[order+1:], tin[order+1:])
                return root

class treeNode:
    def __init__(self, x):
        self.left = None
        self.right = None
        self.val = x

if __name__ == '__main__':
    flag = "printTreeNode"
    solution = Solution()
    preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]
    middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]
    treeRoot1 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq)
    if flag == "printTreeNode":
        newArray = solution.levelOrder(treeRoot1)
        print(newArray)
            
          

leetcode和劍指offer不同之處是輸出的格式，也很好解決，細(xì)心一下就好。

[[1], [2, 3], [4, 5, 6], [7, 8]]