Re: [問卦] 演算法DFS看得懂 但寫不出來 問題在哪？

本巨巨推薦DFS從binary tree開始寫 並且要用遞迴的方式

用stack可以 但是全局視野比較沒有解子問題的感覺

類似這一題

98. Validate Binary Search Tree

這題就是要你驗證 這是不是一個Binary Search Tree

其實就是不斷解以下這個子問題

1. 左子樹是不是BST

如果不是 那此Binary Tree不是BST

2. 如果左子樹是BST 那根節點的值是不是比左子樹最大的還大

如果不是 那此Binary Tree也不是BST

3. 右子樹是不是BST 並且裡頭所有的值都大於根節點的值

那我們來看一個例子

按照上面的邏輯

5
/ \
3 7
/ \ /
1 4 6

1. 左子樹是不是BST 那我們就要看 3
/ \
1 4

喔喔 還有左子樹 再來看 那 1 是不是BST? 是

那同時用一個變量來存1的值 prev = 1

那再來就是

2. 如果左子樹是BST 那根節點的值是不是比左子樹最大的還大

3 是不是比1大 是 並且更新prev = 3

再來

3. 右子樹是不是BST 並且裡頭所有的值都大於根節點的值

4 是不是 BST? 是 那4是不是比3大? 是

再來更新prev = 4

我們解完 3
/ \
1 4

再來就要看 5
\
7
/
6

解完 5的左子樹了 那就回到

2.如果左子樹是BST 那根節點的值是不是比左子樹最大的還大

剛剛的prev = 4 那5有沒有比4大? 有 更新prev=5

再來就是

3. 右子樹是不是BST 並且裡頭所有的值都大於根節點的值

又是一個子問題

我們要來看 7 的 1. 左子樹是BST
/
6

6是不是BST? 是 有沒有大於5? 有 更新prev=6

2. 如果左子樹是BST 那根節點的值是不是比左子樹最大的還大

7有沒有比6大? 有 更新prev=7

過完整棵樹 發現所有問題的1. 2. 3. 都是true 那我們就可以說這個二元樹是一顆BST

本巨巨覺得DFS的精神就是要你站在子問題的視野來解題 忘掉你從哪裡來

然後從子子子子子子子問題開始解回去

用stack結構來解這題也行 也是DFS 也比較理想

變成一個用stack做inorder traversal

不會讓你stack overflow 也比較快 不用caller callee一直跳

但就少了解子問題的味道 我覺得拉

※ 引述《cosmite (焼き団子)》之銘言：
: 最近開始Leetcode
: 發現字串處理和系統設計的的題目較DFS容易寫
: DFS的題目看解答看得懂
: 但是要自己從無到有寫一次
: 包括邊界條件和遞迴判斷式怎麼寫 卻寫不出來
: （中等難度）
: 到底是哪裡出問題？
: 我是不是題目寫太少了
: 應該從最簡單的DFS題目 反覆不同寫
: 寫到建函示變反射動作嗎？
: 有沒有人能救我==
: 卦
: -----
: Sent from JPTT on my iPhone

--

很正常啊 因為你會用stack啊 對會寫code的人你要他用遞迴還是stack都行

你可以自己刻出stack啊 用雙queue模擬stack 怎麼樣 沒規定時間我也能脫褲子放屁