二叉树遍历

二叉树的遍历算法主要分为两种：递归遍历以及层序遍历。其中递归遍历可以延伸出DFS算法、回溯算法，而层序遍历可以延伸出BFS算法。

递归遍历（DFS）：

递归遍历的代码实现如下：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def traverse(root : TreeNode):
    if root is None:
        return
    # 前序位置
    traverse(root.left)
    # 中序位置
    traverse(root.right)
    # 后序位置

二叉搜索树的遍历结果是有序的。

层序遍历（BFS）：

层序遍历需要借助队列来实现，且根据不同的需要有三种实现方法：

1. 最简单的实现方法：

    from collections import deque
   
    def LevelOrderTraverse(root):
        if root is None:
            return
        q = deque()
        q.append(root)
       
    while q:
        current = q.popleft()
        print (current.value)
           
        if current.left is not None:
            q.append(current.left)
        if current.right is not None:
            q.append(current.right)
   

   • 优点：实现简单，每次仅需要将队头元素取出，将其左右子节点加入队列即可。
   • 缺点：无法知道当前节点在第几层，即无法解决这些问题：该二叉树的最小深度、收集二叉树节点。
2. 因此对以上算法进行改造：

    from collections import deque
   
    def LevelOrderTraverse(root):
        if root is None:
            return
        q = deque()
        q.append(root)
        # 根节点视为第一层
        depth = 1
           
        while q:
            # 需要注意的是sz需要在遍历前记下来，因为在循环的过程中q的长度是会变化的
            sz = len(q)
            for i in range(sz):
                current = q.popleft()
                print (f"Depth = {depth}, Value = {current.value}")
                   
                if current.left is not None:
                    q.append(current.left)
                if current.right is not None:
                    q.append(current.right)
            depth += 1           
   

3. 现在添加一个State类以实现每条树枝权重和为任意值的情况，让每个节点维护自己的权重：

    from collections import deque
   
    class State:
        def __init__(self, node, depth):
            self.node = node
            self.depth = depth
               
    def LevelOrderTraverse(root):
        if root is None:
            return
        q = deque()
        # 根节点的路径权重和是1
        q.append(State(root, 1))
           
        while q:
            current = q.popleft()
            print(f"Depth = {current.depth}, Value = {current.value}")
            if current.node.left is not None:
                q.append(State(current.node.left, current.depth + 1))
                   
            if current.node.right is not None:
                q.append(State(current.node.right, current.depth + 1))
   

其他遍历方式皆是换汤不换药