动画演示|二叉树de深度优先搜索DFS

原理

深度优先搜索（DFS）遵循这样一条准则：总是沿着节点的一条边，一路走到黑，而后返回到出发节点，再继续下一条边，假如找到目标节点，则返回，假如找不到，就会遍历完一律节点。因为二叉树只有两条边，所以DFS对二叉树来说，就是先把左子树遍历完，再遍历右子树，等同于先序遍历。

下面用动画演示了查找5的过程：

DFS动画演示

原理很简单清晰，不过俗话说得好：

细节是魔鬼

下面来看看如何用Swfit实现DFS，给出少量编程中需要注意的问题。

DFS的递归实现

因为递归很符合算法逻辑，首先来看看递归的实现，先定义二叉树的节点：

public class TreeNode {    public var val: Int //节点的值    public var left: TreeNode? //左节点    public var right: TreeNode? //右节点    public init(_ val: Int) {        self.val = val        self.left = nil        self.right = nil    }}

完整的递归实现：

func dfsTree(_ root: TreeNode?, _ dst: Int) -> TreeNode? {    if (root == nil) {        return nil    }    if (root?.val == dst) {        return root    }    var dstNode = self.dfsTree(root?.left, dst)    if (dstNode == nil) {        dstNode = self.dfsTree(root?.right, dst)    }        return dstNode}

因为二叉树本身就是递归定义的，所以用递归调用显得很自然，只需先解决left，再解决right就可。

DFS的非递归实现

因为大部分递归的效率较低，尝试把递归开展为循环，这时有两个问题需要考虑：

1. 因为当左分支访问完成后，要回到节点获取右分支，需要记录访问过的节点，这里用Array作为栈来存储。
2. 节点有三种状态：未访问、已访问、分支都已访问完成。

如动画中演示的，蓝色对应未访问，即树的初始状态；黄色代表节点已访问，已放入栈中；灰色对应左右分支都已访问，又该如何存储呢？为保存左右分支的访问状态，这里连同节点一起用元组保存在栈中：

(node:TreeNode, isCheckLeft:Bool, isCheckRight:Bool)

完整的非递归实现如下：

func loopDfsTree(_ root: TreeNode?, _ dst: Int) -> TreeNode? {    if (root == nil) {        return nil    }    var checkNodes = Array<(node:TreeNode, isCheckLeft:Bool, isCheckRight:Bool)>()    checkNodes.append((root!, false, false))    while checkNodes.last != nil {        var nodeInfo = (checkNodes.popLast())!        let dstNode = nodeInfo.node        if (dstNode.val == dst) {            return dstNode        }        if (dstNode.left != nil && nodeInfo.isCheckLeft == false) {            nodeInfo.isCheckLeft = true            checkNodes.append(nodeInfo)            checkNodes.append(((dstNode.left)!, false, false))        } else if (dstNode.right != nil && nodeInfo.isCheckRight == false) {            nodeInfo.isCheckRight = true            checkNodes.append(nodeInfo)            checkNodes.append(((dstNode.right)!, false, false))        } else {        }    }        return nil}

思考题

比照DFS的递归实现和非递归实现，为什么递归实现不需要保存节点的状态信息？欢迎你的留言，相信经过深度思考的知识，才会历久弥新。