原理

深度优先搜索（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的非递归实现

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

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

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

(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
}