之字形走法的最大長度 Longest ZigZag Path_Leetcode #1372_精選75

Ussama Azam on Unsplash

題目敘述

題目會給我們一顆二元樹的根節點。請問在這棵樹中，之字型走法的路徑長度最大值是多少?

如果無解，請返回 零。

註:

之字型走法就是有一段路徑，都是由連續的 左右左右...，或者 右左右左...所構成的路徑。(看下方的測試範例會更清楚題目的定義)

題目的原文敘述

測試範例

Example 1:

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).

Example 2:

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).

Example 3:

Input: root = [1]
Output: 0 
無解，返回0​

約束條件

Constraints:

• The number of nodes in the tree is in the range [1, 5 * 10^4].

結點總數目介於1 ~ 五萬 之間。

• 1 <= Node.val <= 100

每個節點值都介於1~100之間。

演算法 DFS從上到下，攜帶擺動的方向資訊與擺動長度。

這題的關鍵是之字型的擺動方向。

串接的時候，我們需要知道剛剛從上面下來的是向左走還是向右走，接著可以分析它的結構，再針對子樹進行參數更新，盡量去延長之字型的路徑。

1. 當剛剛從上面往下的時候是向左走