深度优先遍历&广度优先遍历

二叉树的[深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列

深度优先遍历中，具体分为如下三种：

先序遍历：先访问根节点，再遍历左子树，再遍历右子树；
中序遍历：先遍历左子树，再访问根节点，再遍历右子树；
后序遍历：先遍历左子树，再遍历右子树，再访问根节点；

# 定义二叉树节点
class TreeNode(object):
    def __init__(self,val,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right

#定义二叉树类
class BinaryTree(object):
    def __init__(self,root=None):
        self.root=root
 
    def preOrder(self,retList=[],node='root'):
        if node!=None:
            retList.append(node)
            self.preOrder(retList,node.left)　　　　# 递归调用，将左子节点放到列表里　　
            self.preOrder(retList,node.right)　　  # 递归调用，将右节点放到列表里　　
        return retList
    def inOrder(self,retList=[],node='root'):
        if node!=None:
            self.inOrder(retList,node.left)
            retList.append(node)
            self.inOrder(retList,node.right)
        return retList
    def postOrder(self,retList=[],node='root'):
        if node!=None:
            self.postOrder(retList,node.left)
            self.postOrder(retList,node.right)
            retList.append(node)
        return retList

if __name__=='__main__':
    rootNode=TreeNode(50)
    rootNode.left = TreeNode(20,left=TreeNode(15),right=TreeNode(30))
    rootNode.right = TreeNode(60,right=TreeNode(70))
    binaryTree=BinaryTree(rootNode)
    ret = binaryTree.preOrder([],binaryTree.root)
    for i in ret:
        print(i.val,end='.')
    print('\n'+'-'*20)
    ret = binaryTree.inOrder([],binaryTree.root)
    for i in ret:
        print(i.val,end='.')
    print('\n'+'-'*20)
    ret = binaryTree.postOrder([],binaryTree.root)
    for i in ret:
        print(i.val,end='.')

广度优先遍历：

从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

from queue import Queue
 
class TreeNode(object):
    def __init__(self,var,left=None,right=None):
        self.var = var
        self.left = left
        self.right = right
 
class BinaryTree(object):
    def __init__(self,root = None):
        self.root = root

    def breathSearth(self):
        if self.root == None:
            return None
        retList = []
        queue = Queue()
        queue.put(self.root)
        while queue.empty() is not True:
            node = queue.get()
            retList.append(node.var)
            if node.left != None:
                queue.put(node.left)
            if node.right != None:
                queue.put(node.right)
        return retList