深度&广度优先搜索

jskyzero 2020/10/12

本文将以LeetCode的例题为例子，用Python语言实现深度优先、广度优先搜索。

DFS/深度优先

例题：Increasing Order Search Tree

题意：前序深度优先遍历即可。

因为要求一个特定的输出格式，所以先简单实现这部分的逻辑

    def saveResult(self, node: TreeNode) -> None:
        if node == None: return
        # print(node.val)

        if self.result == None:
            self.result = TreeNode(node.val, None, None)
            self.resultTop = self.result
        else:
            self.resultTop.right = TreeNode(node.val, None, None)
            self.resultTop = self.resultTop.right

递归形式的深度优先很好写：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        self.result = None
        self.dfs(root)
        return self.result

    def dfs(self, root: TreeNode) -> None:
        if root == None: return
        self.dfs(root.left)
        self.saveResult(root)
        self.dfs(root.right)

简单来说，注意None的判断，以及是前序中序还是后序就行。

这里也提供一个用栈替代递归实现的版本：

    def dfs(self, root: TreeNode) -> None:
        if root == None: return
        stack = [root]

        while (len(stack) != 0):

            top = stack.pop()
            # print(len(stack))

            if top.left == None and top.right == None:
                self.saveResult(top)
            else:
                left = top.left
                right = top.right
                top.left = None
                top.right = None

                if right != None: stack.append(right)
                stack.append(top)
                if left != None: stack.append(left)

简单来说，用栈的是否为空来一直遍历，取出栈的首个元素，并按照顺序反向压进栈即可。

有一个需要注意的事情是这里将处理的栈定元素手动变成了叶子节点重新压栈，因为不是中序遍历，后续再处理到这个元素如果没有取出左右相连节点，会再次将左右相连节点压栈从而死循环。

BFS/广度优先

例题：Symmetric Tree

题意：对根节点右边的子树进行反向的遍历与左边比较即可。

这里其实不一定严格要广度优先，不过广度优先是最普遍的遍历树的打印方式。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None: return True
        left = []
        right = []
        self.bfsLeft(root.left, left)
        self.bfsRight(root.right, right)

        # print(left)
        # print(right)
        return left == right

    def bfsLeft(self, root: TreeNode, result: list):
        queen = [root]

        while len(queen) != 0:
            top = queen.pop(0)

            if top != None:
                result.append(top.val)
                queen.append(top.left)
                queen.append(top.right)
            else:
                result.append(None)

        return result

    def bfsRight(self, root: TreeNode, result: list):
        queen = [root]

        while len(queen) != 0:
            top = queen.pop(0)

            if top != None:
                result.append(top.val)
                queen.append(top.right)
                queen.append(top.left)
            else:
                result.append(None)

        return result

用队列实现，其实还算简单，不过这里因为空值也要比较所以空值的处理方式不太一样。

当然也可以用递归形式的DFS实现：

    def bfsLeft(self, top: TreeNode, result: list):        

        if top != None:
            result.append(top.val)
            self.bfsLeft(top.left, result)
            self.bfsLeft(top.right, result)                
        else:
            result.append(None)

        return result

    def bfsRight(self, top: TreeNode, result: list):        

        if top != None:
            result.append(top.val)
            self.bfsRight(top.right, result) 
            self.bfsRight(top.left, result)                          
        else:
            result.append(None)

        return result

如果硬要用递归本质的DFS来模仿BFS的打印的话，可以考虑引入额外的标记字段 不过就有点得不尝试，毕竟DFS很容易爆栈，而BFS则可以比较方便的控制队列大小。