leetcode地址：二叉樹中的最長交錯路徑
給你一棵以 root 為根的二叉樹，二叉樹中的交錯路徑定義如下：

選擇二叉樹中 任意 節點和一個方向（左或者右）。
如果前進方向為右，那么移動到當前節點的的右子節點，否則移動到它的左子節點。
改變前進方向：左變右或者右變左。
重復第二步和第三步，直到你在樹中無法繼續移動。
交錯路徑的長度定義為：訪問過的節點數目 - 1（單個節點的路徑長度為 0 ）。

請你返回給定樹中最長 交錯路徑 的長度。

示例 1：

輸入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
輸出：3
解釋：藍色節點為樹中最長交錯路徑（右 -> 左 -> 右）。
示例 2：

輸入：root = [1,1,1,null,1,null,null,1,1,null,1]
輸出：4
解釋：藍色節點為樹中最長交錯路徑（左 -> 右 -> 左 -> 右）。
示例 3：

輸入：root = [1]
輸出：0

提示：

每棵樹最多有 50000 個節點。
每個節點的值在 [1, 100] 之間。

實現思路

實現最長交錯路徑（Longest ZigZag Path）的問題涉及在二叉樹中找到一條路徑，該路徑上的每一步都在左右子樹之間交替。具體來說，路徑從根節點開始，每次選擇左子節點或右子節點，但不能連續兩次選擇同一個方向。最長交錯路徑的長度是這條路徑上邊的數量。

代碼詳解

1. 定義數據結構
   首先，定義一個二叉樹節點的類，用于表示樹中的每個節點。

class TreeNode:def __init__(self, value=0, left=None, right=None):self.value = valueself.left = leftself.right = right

2. 初始化類和變量
   在解決方案類中，定義一個變量來記錄最長交錯路徑的長度，并初始化該類。

class Solution:def __init__(self):self.max_length = 0

3. 定義遞歸函數
   使用深度優先搜索（DFS）來遍歷二叉樹。在每個節點，記錄當前路徑的長度，并更新最長交錯路徑的長度。定義遞歸函數 dfs 來處理這個過程。

def dfs(node, direction, length):if not node:returnself.max_length = max(self.max_length, length)if direction == 'left':dfs(node.left, 'left', 1)  # 重置左邊路徑長度dfs(node.right, 'right', length + 1)  # 繼續增加右邊路徑長度else:dfs(node.left, 'left', length + 1)  # 繼續增加左邊路徑長度dfs(node.right, 'right', 1)  # 重置右邊路徑長度

4. 調用遞歸函數
   在主函數 longestZigZag 中，從根節點開始，以左和右兩個方向調用遞歸函數 dfs。

def longestZigZag(self, root: TreeNode) -> int:dfs(root, 'left', 0)dfs(root, 'right', 0)return self.max_length

5. 將上述步驟組合成完整的代碼：

class TreeNode:def __init__(self, value=0, left=None, right=None):self.value = valueself.left = leftself.right = rightclass Solution:def __init__(self):self.max_length = 0def longestZigZag(self, root: TreeNode) -> int:def dfs(node, direction, length):if not node:returnself.max_length = max(self.max_length, length)if direction == 'left':dfs(node.left, 'left', 1)  # 重置左邊路徑長度dfs(node.right, 'right', length + 1)  # 繼續增加右邊路徑長度else:dfs(node.left, 'left', length + 1)  # 繼續增加左邊路徑長度dfs(node.right, 'right', 1)  # 重置右邊路徑長度dfs(root, 'left', 0)dfs(root, 'right', 0)return self.max_length# 示例二叉樹
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(5)
root.left.right.right = TreeNode(6)# 計算最長交錯路徑
solution = Solution()
result = solution.longestZigZag(root)
print("最長交錯路徑長度:", result)

關鍵點總結
二叉樹節點類：用于表示樹的結構。
深度優先搜索（DFS）：用于遍歷二叉樹。
遞歸：在每個節點記錄路徑的長度，并更新最長交錯路徑的長度。
方向標志：用 direction 參數來指示當前路徑的方向（左或右），并在遞歸調用時進行交替。
路徑長度記錄：用 length 參數來記錄當前路徑的長度，并更新 self.max_length 以記錄最長路徑的長度。
通過這些步驟，可以有效地計算出二叉樹中最長的交錯路徑。

GO語言實現

package mainimport "fmt"// TreeNode 表示二叉樹的節點
type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}// Solution 結構體用于記錄最長交錯路徑的長度
type Solution struct {maxLength int
}// NewSolution 初始化 Solution
func NewSolution() *Solution {return &Solution{maxLength: 0}
}// dfs 遞歸函數遍歷二叉樹
func (s *Solution) dfs(node *TreeNode, direction string, length int) {if node == nil {return}// 更新最長路徑長度if length > s.maxLength {s.maxLength = length}if direction == "left" {s.dfs(node.Left, "left", 1)         // 重置左邊路徑長度s.dfs(node.Right, "right", length+1) // 繼續增加右邊路徑長度} else {s.dfs(node.Left, "left", length+1)  // 繼續增加左邊路徑長度s.dfs(node.Right, "right", 1)       // 重置右邊路徑長度}
}// LongestZigZag 計算二叉樹的最長交錯路徑
func (s *Solution) LongestZigZag(root *TreeNode) int {s.dfs(root, "left", 0)s.dfs(root, "right", 0)return s.maxLength
}func main() {// 構建示例二叉樹root := &TreeNode{Val: 1}root.Left = &TreeNode{Val: 2}root.Right = &TreeNode{Val: 3}root.Left.Right = &TreeNode{Val: 4}root.Left.Right.Left = &TreeNode{Val: 5}root.Left.Right.Right = &TreeNode{Val: 6}// 計算最長交錯路徑solution := NewSolution()result := solution.LongestZigZag(root)fmt.Println("最長交錯路徑長度:", result)
}

kotlin實現

class TreeNode(val value: Int) {var left: TreeNode? = nullvar right: TreeNode? = null
}class Solution {private var maxLength = 0private fun dfs(node: TreeNode?, direction: String, length: Int) {if (node == null) return// 更新最長路徑長度if (length > maxLength) {maxLength = length}if (direction == "left") {dfs(node.left, "left", 1)       // 重置左邊路徑長度dfs(node.right, "right", length + 1) // 繼續增加右邊路徑長度} else {dfs(node.left, "left", length + 1)  // 繼續增加左邊路徑長度dfs(node.right, "right", 1)     // 重置右邊路徑長度}}fun longestZigZag(root: TreeNode?): Int {dfs(root, "left", 0)dfs(root, "right", 0)return maxLength}
}fun main() {// 構建示例二叉樹val root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left?.right = TreeNode(4)root.left?.right?.left = TreeNode(5)root.left?.right?.right = TreeNode(6)// 計算最長交錯路徑val solution = Solution()val result = solution.longestZigZag(root)println("最長交錯路徑長度: $result")
}