二元搜尋樹合法順序問題 - 考試

※ 引述《aishafyh (Aisha)》之銘言：
: 中國鋼鐵104年的資訊工程考科中的第34題
: 題目為：
: 請回答下列各序列(sequence)可否構成二元搜尋樹
: (binary search tree)搜尋鍵值363 的合法順序。
: (1) 2,252,401,398,330,344,397,363
: (2) 924,220,911,244,898,258,362,363
: (3) 925,202,911,240,912,245,363
: (4) 2,399,387,219,266,382,381,278,363
: (5) 935,278,347,621,299,392,358,363
: 有上網搜尋過，沒有看到類似的解題方式，
: 希望有大大可以幫忙解一下這題，
: 可以的話煩請附一下計算過程
: 感謝各位 ^_^
: 祝大家金榜題名


提供一下想法，判斷一棵BST是否合法最普通的做法就是畫畫看

在畫的同時也要看是否滿足BST的條件

以(1)為例
(1) 2,252,401,398,330,344,397,363

2
\
252
\
401
/
398
/ <= 找到363且符合BST的條件，所以這是一棵BST
330
\
344
\
397
/
363


底下僅列出不合法的選項

(3) 925,202,911,240,912,245,363

925
/
202
\
911
/
240
\
912 <= 912>911卻在911的左子樹，所以(3)不合法


(5) 935,278,347,621,299,392,358,363

935
/
278
\
347
\
621
/
299 <= 299<347卻在347的右子樹，所以(5)不合法


有錯煩請指正，希望能幫助到有疑惑的人。

大家一起加油吧!


--