> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/notes-of-algorithms/shen-du-xian-sou-depthfirst-search.md).

# 深度優先搜尋 (Depth-first Search)

## 1.Introduction

* 是一種圖形(graph)搜索演算法
* 以樹(tree)來說, 就是先遇到的node就先Visiting

## **2.完整程式碼**

```
    TreeNode * dfsTraverse(TreeNode * root, TreeNode * p , TreeNode * q)
    {
        //一般來說, 我們會希望一旦DFS函式到達樹的底部就返回, 
        //因此慣例上會判斷TreeNode是否為NULL, 
        //而dfsTraverse又希望一旦找到p, q節點就返回
        if( root == p || root == q || root == NULL)
        {
            return root;
        }
        
        //一般來說會將左右節點作為新的root再次進行迭代, 差別只有在順序, 
        //依需求來決定是LVR, LRV, 還是VLR
        TreeNode * parent1 = dfsTraverse(root->left, p, q);
        TreeNode * parent2 = dfsTraverse(root->right, p, q);
        
        //可以想像成當觸底返回後的sub tree, 我們希望對它做什麼事, 
        //例如我們希望取得Common Ancestor, 因此回傳parent
        if( parent1 && parent2)
        {
            return root;
        }
        else
        {
            return parent1 ? parent1:parent2;
        }
    }
```

## **3.解析**

* 當我們的目的是必須遍歷整棵樹才能取得的結果, 例如[Lowest Common Ancestor of a Binary Tree](https://jenhsuan.gitbooks.io/letcode/content/leetcode236-lowest-common-ancestor-of-a-binary-tree.html), [Pre-Order Traversal](https://jenhsuan.gitbooks.io/letcode/content/3data-structure/33binary-tree/331binary-tree-traversal.html), 或是取得sub tree等問題時, DFS是一個常見的做法, 概念上是藉著recursive的方式快速到達樹的端點, 一旦到達樹的端點, recursive函式就會開始返回 

##