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

1.Introduction

• 是一種圖形(graph)搜索演算法

• 以樹(tree)來說, 就是先遇到的node就先Visiting

2.解析

• 當我們的目的是必須遍歷整棵樹才能取得的結果, 例如Lowest Common Ancestor of a Binary Tree, Pre-Order Traversal, 或是取得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, LRV, 還是VLR

      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

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