前往
大廳
主題

LeetCode - 671. Second Minimum Node In a Binary Tree 解題心得

Not In My Back Yard | 2020-12-17 00:00:05 | 巴幣 0 | 人氣 197

題目連結:


題目意譯:
給定一個特殊的非空二元樹,其由多個含有非負值節點所組成,且樹中的每個節點只會有恰好兩個或是零個子節點。如果有一個節點有兩個子節點,則該節點值必為兩個子節點之值中最小之值。更正式地說是,root.val = min(root.left.val, root.right.val) 這個性質永遠成立。

給定一棵這樣子的二元樹,你需要輸出整棵樹的節點之值所形成的集合中節點值第二大為何。

如果沒有第二大的值存在,則輸出「-1」。

限制:
樹的節點數位於範圍 [1, 25] 中。
1 ≦ Node.val ≦ 231 - 1
對於樹的每個內部節點,滿足 root.val == min(root.left.val, root.right.val)



範例測資:
範例 1:
輸入: root = [2,2,5,null,null,5,7]
輸出: 5
解釋: 最小的值為 2 ,第二小的值為 5 。

範例 2:
輸入: root = [2,2,2]
輸出: -1
解釋: 最小的值為 2 ,但是不存在第二小的值。


解題思維:
就是單純地逛過每個節點然後在探訪的同時一併更新最大值以及第二大的值。掃完之後,如果沒有第二大的就回傳 -1;反之,回傳第二大的值。




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

創作回應

更多創作