深度優先搜尋 (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, Pre-Order Traversal, 或是取得sub tree等問題時, DFS是一個常見的做法, 概念上是藉著recursive的方式快速到達樹的端點, 一旦到達樹的端點, recursive函式就會開始返回