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

## 1.Introduction

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

## 2.解析

* 當我們的目的是必須遍歷整棵樹才能取得的結果, 例如[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函式就會開始返回
* DFS函式(用在binary tree的DFS)可以解析成幾個部份, 以`TreeNode * dfsTraverse(TreeNode * root, TreeNode * p , TreeNode * q)`這個函式為例: 
  * 1.觸底的限制: 
    * 一般來說, 我們會希望一旦DFS函式到達樹的底部就返回, 因此慣例上會判斷TreeNode是否為NULL, 而dfsTraverse又希望一旦找到p, q節點就返回, 因此會加上這段:

      ```
      if( root == p || root == q || root == NULL)
      {
        return root;
      }
      ```
  * 2.讓DFS向下搜尋:
    * 一般來說會將左右節點作為新的root再次進行迭代, 差別只有在順序, 依需求來決定是[LVR](https://jenhsuan.gitbooks.io/letcode/content/3data-structure/33binary-tree/331binary-tree-traversal.html), [LRV](https://jenhsuan.gitbooks.io/letcode/content/3data-structure/33binary-tree/331binary-tree-traversal.html), 還是[VLR](https://jenhsuan.gitbooks.io/letcode/content/3data-structure/33binary-tree/331binary-tree-traversal.html)

      ```
      TreeNode * parent1 = dfsTraverse(root->left, p, q);
      TreeNode * parent2 = dfsTraverse(root->right, p, q);
      ```
  * 3.DFS函式主要執行的內容:
    * 可以想像成當觸底返回後的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)

```
TreeNode * dfsTraverse(TreeNode * root, TreeNode * p , TreeNode * q)
    {
        if( root == p || root == q || root == NULL)
        {
            return root;
        }
        TreeNode * parent1 = dfsTraverse(root->left, p, q);
        TreeNode * parent2 = dfsTraverse(root->right, p, q);
        if( parent1 && parent2)
        {
            return root;
        }
        else
        {
            return parent1 ? parent1:parent2;
        }
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jen-hsuan-hsieh.gitbook.io/letcode/2.algorithm/28-shen-du-you-xian-sou-xun-depth-first-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.