算法学习：打印二叉树

–

四种主要的遍历思想为：

前序遍历：根结点 —> 左子树 —> 右子树

中序遍历：左子树—> 根结点 —> 右子树

后序遍历：左子树 —> 右子树 —> 根结点

层次遍历：只需按层次遍历即可

例如，求下面二叉树的各种遍历

前序遍历：1  2  4  5  7  8  3  6 

中序遍历：4  2  7  5  8  1  3  6

后序遍历：4  7  8  5  2  6  3  1

层次遍历：1  2  3  4  5  6  7  8

–

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

解题思路

条件反射地想通过递归解决，结果硬是没有找到合适的解决思路，也许递归的方式不是很适合这种类型的题目吧~

利用队列的先进先出(FIFO)特性解决。每从队列头部获取一个节点，就将该节点的左右子节点存入队列的尾部。如此往复，直至队列为空。这篇博客内的图片和表格很形象的展示了程序运行过程中队列内值的变化过程：

二叉树样例：

打印二叉树每层节点时队列内值的变化：

Python代码

def PrintFromTopToBottom(self, root):
    queue = []
    result = []
    if root == None:
        return result

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

带测试的Python代码：

根据前序遍历和中序遍历，打印二叉树

class Solution:
   #从上往下打印出二叉树的每个节点，同层节点从左至右打印
    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

    # 给定二叉树的前序遍历和中序遍历，获得该二叉树
    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)

–

参考：https://blog.csdn.net/u010005281/article/details/79493413

–