1372. Longest ZigZag Path in a Binary Tree

[fockspaces]

此題不能對每個 node 都 DFS 一遍，會 TTL 因此想到另一個方法，和求 tree height 有點像，在 DFS 過程更新 ans，並將必要資訊回傳 DFS 會將左右拐點的最大長度回傳，左子能接其右拐，反之

1. base case：空節點，回傳 0, 0
2. 每次都對左右子抓銜接點，left_zig, right_zig，並將其接上自身 (+1）回傳
3. 更新 ans，規則為左右子節點的長度 - 1 與 ans 比較

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        def DFS(root):
            nonlocal ans
            if not root:
                return 0, 0    
            left_zig, _ = DFS(root.left)
            _, right_zig = DFS(root.right)
            longest_from_root = max(left_zig, right_zig)
            ans = max(ans, longest_from_root)
            return right_zig + 1, left_zig + 1
        ans = 0   
        DFS(root)
        return ans

[fockspaces]

GPT improve:

1. 拿掉 nonlocal，直接用 self 來作為參數
2. 這邊 DFS 回傳的是 root 底下的 zig 節點數，剛好為 root 的 zigzag 總長，更新 ans 不需額外 + 1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        def DFS(root):
            if not root:
                return 0, 0    
            left_zig, _ = DFS(root.left)
            _, right_zig = DFS(root.right)
            self.ans = max(self.ans, left_zig, right_zig)
            return right_zig + 1, left_zig + 1
        DFS(root)
        return self.ans