前往
大廳
主題

LeetCode - 993. Cousins in Binary Tree 解題心得

Not In My Back Yard | 2021-03-02 21:58:39 | 巴幣 0 | 人氣 332

題目連結:


題目意譯:
在一棵二元樹中,根節點為深度 0 ,且每個深度 k 之節點的子節點為深度 k + 1 。

兩個樹中的節點被稱作堂兄弟節點,如果他們有著相同的深度但是兩者父節點不一樣。

(翻譯注解:上述的堂兄弟英文稱呼為 Cousins,其正確意思為堂表兄弟姊妹。但是因為 Parent Node 多譯作父節點,因為從父方所以為「堂」,兄弟則是因為男性為主(中文稱呼時常以男性為主)。)

給定我們一棵節點值皆相異的二元樹之根節點 root,以及兩個相異值 x 、 y 代表樹中的兩個相異節點。

回傳真(True)若且唯若對應 x 、 y 的值之兩節點為堂兄弟節點。

限制:
樹上的節點數介於 2 和 100 之間。
每個節點值皆相異且介於 1 ~ 100 之間。



範例測資:
範例 1:
輸入: root = [1,2,3,4], x = 4, y = 3
輸出: false

範例 2:
輸入: root = [1,2,3,null,4,null,5], x = 5, y = 4
輸出: true

範例 3:
輸入: root = [1,2,3,null,4], x = 2, y = 3
輸出: false


解題思維:
這題有兩種思路,一種是廣度優先搜尋(Breadth First Search,BFS)、另一個是深度優先搜尋(Depth First Search,DFS)。

BFS 就是直接從根節點開始慢慢一層一層地擴張(不過通常需要特別紀錄目前的深度)直到碰到節點 x 以及節點 y,過程中可以得知它們的深度以及父節點。所以找到這兩個節點之後,直接判斷深度是否一樣且父節點是否相異。如果是就回傳真;反之,回傳假(False)。

而 DFS 的深度等同於遞迴深度(可以參數形式傳遞),所以當碰到節點 x 以及節點 y 時的遞迴深度即是它們的深度;而父節點可以在進去下一層遞迴提前將該父節點的子節點之父節點(也就是目前的節點)特別紀錄下來。同樣地,找到節點 x 和節點 y 的深度和父節點便可判斷(如 BFS)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作