1. 什么是深度優(yōu)先搜索算法

深度優(yōu)先搜索（Depth-first Search）對(duì)應(yīng)于廣度優(yōu)先搜索（Breadth-first Search），是一種可應(yīng)用于樹的遍歷的算法，常見的深度優(yōu)先遍歷方式分為先序遍歷、中序遍歷和后序遍歷。
以上定義對(duì)于從未接觸樹這種數(shù)據(jù)結(jié)構(gòu)的人而言實(shí)在是生僻難懂，所以一圖勝千言。
假設(shè)有如下一顆二叉樹：

一顆二叉樹

1. 自身 > 左子 > 右子（先序遍歷，此處“先”對(duì)應(yīng)自身的優(yōu)先級(jí)）
2. 左子 > 自身 > 右子（中序遍歷）
3. 左子 > 右子 > 自身 （后序遍歷）

對(duì)于1，遍歷順序?yàn)?1 -> 2 -> 4 -> 5 -> 3 -> 6；
對(duì)于2，遍歷順序?yàn)?4 -> 2 -> 5 -> 1 -> 3 -> 6；
對(duì)于3，遍歷順序?yàn)?4 -> 5 -> 2 -> 6 -> 3 -> 1；

從以上的三種思路中可以看出，與廣度優(yōu)先搜索的一層層向下訪問的邏輯不同，這里每次我們都要一直沿著某一條路徑訪問到二叉樹的最底層、直至沒有左右子節(jié)點(diǎn)，才會(huì)返回上層再繼續(xù)下一優(yōu)先級(jí)的訪問，這是我們稱之深度優(yōu)先搜索的原因。

2. 什么是剪枝

樹的節(jié)點(diǎn)有一些額外屬性，在遍歷樹的過程中，同時(shí)判斷節(jié)點(diǎn)的屬性，并刪除不符合屬性要求的分支節(jié)點(diǎn)，稱為剪枝。比如我們?cè)O(shè)置一個(gè)屬性為“在廣度優(yōu)先遍歷中的順序”，即途中節(jié)點(diǎn)中的數(shù)字，我們要找出上面那顆二叉樹中所有滿足“廣度優(yōu)先順序小于5”的節(jié)點(diǎn)，那么先序遍歷過程為：1 -> 2 -> 4 -> 5（刪） -> 3 -> 6（刪），先序遍歷最終結(jié)果為：1 -> 2 -> 4 -> 3。

3. 一道產(chǎn)品面試題：為失明者設(shè)計(jì)一個(gè)鬧鐘

拿到這道題之后，首先考慮四要素：

• WHO it works for——失明者
• WHAT it exactly is——鬧鐘
• WHEN&WHERE it should be used——日常家用
• WHY it's necessary——常規(guī)鬧鐘對(duì)失明者而言存在使用困難

3. 1. 第一點(diǎn)，產(chǎn)品所服務(wù)的對(duì)象，分析失明者人群具體如何分類。

失明者可以分為：

• 先天失明和后天失明
• 不完全失明和完全失明
• 兒童、成人和長者
• 等等

想到這里，我們可以和面試官嘗試溝通并表達(dá)如下看法，爭(zhēng)取獲得他的認(rèn)可：

• • 先天失明與后天失明的區(qū)別在于失明者是否能“腦補(bǔ)”出一些畫面，不是主要矛盾；
• • 還尚存能看清鬧鐘的視力的失明者也不是我們產(chǎn)品服務(wù)的對(duì)象；
• • 兒童和長者在面對(duì)鬧鐘時(shí)與成年人并無本質(zhì)區(qū)別。

因此在大部分情況下，我們面對(duì)的是完全失明的成人。

3. 2. 第二點(diǎn)，產(chǎn)品的本質(zhì)，分析產(chǎn)品定位的分類。

鬧鐘可以分為：

• 家用鬧鐘、隨身鬧鐘
• 電子鬧鐘、指針鬧鐘
• 實(shí)體鬧鐘、軟件鬧鐘
• 電池鬧鐘、充電鬧鐘
• 等等
• • 失明者在外出時(shí)如果有獲取時(shí)間等需求，可以借助外人的幫助；
• • 用于手機(jī)的軟件鬧鐘對(duì)于失明者的不友好程度可能比有按鍵旋鈕的實(shí)體鬧鐘更高；
• • 指針鬧鐘如果采用觸摸指針的方式獲取時(shí)間，因?yàn)榉磸?fù)觸摸可能影響耐用性，而且指針鬧鐘的初衷是采用可視化反饋大部分信息，電子鬧鐘在應(yīng)對(duì)失明者的特殊需求上更為靈活；
• • 至于還是指針鬧鐘至于是電池鬧鐘還是充電鬧鐘，我們可以先繼續(xù)向后思考。

3. 3. 第三點(diǎn)，產(chǎn)品應(yīng)用場(chǎng)景，分析產(chǎn)品被使用的場(chǎng)景分類。

鬧鐘可以用于：

• 叫醒
• 提醒辦事（吃藥等）
• 倒計(jì)時(shí)
• 獲取時(shí)間
• 等等
  這些都是可能會(huì)用到的場(chǎng)景。

3. 4. 第四點(diǎn)，產(chǎn)品需求點(diǎn)，結(jié)合常規(guī)鬧鐘的基本功能，綜述分析產(chǎn)品可能的潛在需求所在。

基本需求：

• 增加盲文說明及按鍵文字
• 獲取現(xiàn)在的時(shí)間
• 提醒將來的時(shí)間
• 開關(guān)機(jī)
• 是否低電量
• 關(guān)閉當(dāng)前鬧鐘
• • 盲文對(duì)于失明者的使用是基本需求；
• • 采用語音報(bào)時(shí)滿足失明者獲取時(shí)間的需求；
• • 還有一些視覺反饋的非0即1功能，比如開關(guān)機(jī)、是否低電量、是否已設(shè)置鬧鐘、關(guān)閉當(dāng)前鬧鐘等也需要設(shè)置觸覺或者聽覺反饋。

高級(jí)需求：

• 倒計(jì)時(shí)

• 整點(diǎn)報(bào)時(shí)

• 鬧鐘重復(fù)

• 語音備注鬧鐘

• 已有鬧鐘播報(bào)

• 小睡模式

• 震動(dòng)提醒

• 無線充電

• • 失明者無法使用一些電器的倒計(jì)時(shí)功能，比如煮飯、微波爐熱菜等；
• • 失明者在設(shè)置時(shí)可以語音備注“吃XX藥”“做午飯”，鬧鐘到時(shí)提醒會(huì)一并播報(bào)語音備注；
• • 鬧鐘重復(fù)功能可對(duì)某一定點(diǎn)提醒設(shè)置重復(fù)規(guī)則，比如每天重復(fù)、每周重復(fù)等；
• • 失明者可以通過已有鬧鐘播報(bào)來查看當(dāng)前設(shè)置的所有鬧鐘；
• • 鬧鐘提醒后，啟動(dòng)小睡模式推遲5分鐘再次提醒；
• • 失明者因?yàn)閾?dān)心鬧鐘吵到同居其他人等原因可設(shè)置為震動(dòng)提醒；
• • 鬧鐘如果不采用電池供電而是充電模式，在低電提醒響起后，失明者將鬧鐘放置在無線充電器周圍，鬧鐘開始充電并發(fā)出反饋。

4. 結(jié)果分析

到這里，對(duì)于如何為失明者設(shè)計(jì)一個(gè)產(chǎn)品的問題，我們已經(jīng)總結(jié)為一系列需求。

以上這類產(chǎn)品經(jīng)理面試題，從題目逐漸分析直至得出結(jié)論的思維過程，也就是本題的考察重點(diǎn)所在。

回過頭看上述思路，如果將原問題視為樹的根節(jié)點(diǎn)，具體的功能點(diǎn)視為樹的最底層節(jié)點(diǎn)，我們的每一次發(fā)散思維都在產(chǎn)生更多節(jié)點(diǎn)、每一次向本質(zhì)分析都在增加樹的深度，當(dāng)我們找出當(dāng)前并列的很多分析角度（也就是樹的當(dāng)層所有節(jié)點(diǎn)）之后，都會(huì)從第一個(gè)節(jié)點(diǎn)向下分析（深度優(yōu)先搜索），直至其不符合我們的想法，便將其剔除（剪枝），一個(gè)節(jié)點(diǎn)及其所有子節(jié)點(diǎn)處理完后再分析同層次的下一個(gè)節(jié)點(diǎn)及其子節(jié)點(diǎn)。

在常規(guī)的廣度優(yōu)先搜索的分析方式中，每一層次都在無限發(fā)散而產(chǎn)生大量可能性、重要性不同的分析角度都需要一并發(fā)散，產(chǎn)生大量無用功（比如我們甚至要分析指針鬧鐘撥指針時(shí)的盲文怎么設(shè)計(jì)等等），直至可能性眾多龐雜使我們無法繼續(xù)向下層分析。

相比較而言，我們可以發(fā)現(xiàn)，深度優(yōu)先搜索+剪枝這樣一邊發(fā)散、一邊精簡(jiǎn)可能性、并將結(jié)論反饋到同層下一個(gè)分析角度的分析問題的思維方法，能避免無用功、幫助收攏發(fā)散的思路、維持分析問題邏輯的一致性。