二叉树的深度优先遍历

基本概念

深度优先遍历（DFS)：沿着一条路径一直找到最深的节点，当没有子节点后，返回上一级节点（并不会区去重新遍历一遍），寻找另外的子节点，继续向下遍历，直到所有节点都被遍历到，并且节点只能被访问一次。

基本思路

（1） 首先将根节点A压入栈中:[A]
（2） 将A节点弹出，找到A节点的两个子节点左孩子B、右孩子C，首先压入B节点，再压入C，[B,C]
（3） 弹出B节点，将B节点的左右节点左孩子D、右孩子E，先把右孩子E入栈，再把左孩子D入栈；[D,E,C]
（4） 弹出D节点，D没有子节点，不压入；[E,C]
（5） 弹出E节点，E的右子树I，压入；[I,C]
如此操作，直到栈中没有节点。

python代码实现(默认优先访问左孩子）

class Node(object):
    """初始化节点"""
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def DFS(root):
    res = []
    tmp = [root]
    if root == None:
        return res
    while tmp!=[]:
        res.append(root.val)#把首部的值放入结果中
        if root.right:
            tmp.insert(0，root.right)
        if root.left:
            tmp.insert(0，root.left)
        if not tmp:
            root = tmp.pop(0)
    return res

参考来源：

https://www.cnblogs.com/xiaolovewei/p/7763867.html
https://blog.csdn.net/XTAOTWO/article/details/83625586