前往
大廳
主題

LeetCode - 1372. Longest ZigZag Path in a Binary Tree 解題心得

Not In My Back Yard | 2024-03-01 12:00:20 | 巴幣 0 | 人氣 46

題目連結:


題目意譯:
你被給定一棵二元樹的根節點 root。

一棵二元樹中一個之字形(Zig-Zag)路徑定義如下:
    選定二元樹中任一節點以及一個方向(往右或往左)。
    如果當前方向為往右,則移動至當前節點的右小孩;反之,則移動到左小孩。
    將方向從往右變成往左,或是從往左變成往右。
    重複第二和第三步直到無法在樹中移動為止。

之字形長度定義為探訪過的節點數量 - 1(單一節點之路徑長度為 0)。

回傳樹中包含的之字形路徑之最長長度。

限制:
樹中節點數位於範圍 [1, 5 × 10 ^ 4]。
1 ≦ Node.val ≦ 100



範例測資:
範例 1:
輸入: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
輸出: 3
解釋: 最長的之字形路徑以藍色節點表示(右 → 左 → 右)。

範例 2:
輸入: root = [1,1,1,null,1,null,null,1,1,null,1]
輸出: 4
解釋: 最長的之字形路徑以藍色節點表示(左 → 右 → 左 → 右)。

範例 3:
輸入: root = [1]
輸出: 0


解題思維:
其實跟求樹的深度差不多(參見這題),只是每個節點不是只有「深度值」而是分成「往左後可以走多深」(當然這是以之字形的方式來走的前提下)、「往右可以走多深」兩個數值(稱其為 L 和 R)。而如此一來,每個節點的 L 值只要看其左小孩的 R 值加上 1、R 值只要看其右小孩的 L 值加上 1 便可以求得。

而所求即為每個節點的 L 、 R 值中的最大值(不過可能會根據選定的遞迴停止條件而需要多減 1,參見範例程式碼)。




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

創作回應

更多創作