[理工] OBST問題

[AAQ8 ()]

https://i.imgur.com/YVKnQ1R.jpg
https://i.imgur.com/64mPnlX.jpg

想問這題最後在建樹的時候

a2要怎麼知道是a1的左兒子還是右兒子


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.65.175
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549798869.A.039.html
推 skyHuan: 看root表格，root[1,4]=3表示v1到v4樹要以v3當root，所以
→ skyHuan: 左邊就是v1到v2子樹，右邊就是v4到v4子樹，要分別去看roo
→ skyHuan: t[1,2]跟root[4,4]是多少決定誰要當子樹的root
→ MumiMumi5566: 他是BST,如果a1是root的時候a2只能放在右子樹
推 skyHuan: 乾抱歉XD 我發現我答非所問...我以為是問誰當root
→ rockieloser: 放左右答案總和會不一樣？
→ rockieloser: 有道理 他是BST==
→ MumiMumi5566: 主要他是BST,而且如果今天a1a2下面不是nil還有其他n
→ MumiMumi5566: ode的話，總合就有可能不一樣吧～
推 anonimo: 做inorder traversal a1~4的順序不會變吧
→ anonimo: 所以2一定在1的右邊
→ AAQ8: 哦哦那我明白了 感謝各位