Skip to content

1372. Longest ZigZag Path in a Binary Tree 👍

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct T {
  int leftMax;
  int rightMax;
  int subtreeMax;
};

class Solution {
 public:
  int longestZigZag(TreeNode* root) {
    return dfs(root).subtreeMax;
  }

 private:
  T dfs(TreeNode* root) {
    if (root == nullptr)
      return {-1, -1, -1};
    const T left = dfs(root->left);
    const T right = dfs(root->right);
    const int leftZigZag = left.rightMax + 1;
    const int rightZigZag = right.leftMax + 1;
    const int subtreeMax =
        max({leftZigZag, rightZigZag, left.subtreeMax, right.subtreeMax});
    return {leftZigZag, rightZigZag, subtreeMax};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int longestZigZag(TreeNode root) {
    return dfs(root).subtreeMax;
  }

  private record T(int leftMax, int rightMax, int subtreeMax) {}

  private T dfs(TreeNode root) {
    if (root == null)
      return new T(-1, -1, -1);
    T left = dfs(root.left);
    T right = dfs(root.right);
    final int leftZigZag = left.rightMax + 1;
    final int rightZigZag = right.leftMax + 1;
    final int subtreeMax =
        Math.max(Math.max(leftZigZag, rightZigZag), Math.max(left.subtreeMax, right.subtreeMax));
    return new T(leftZigZag, rightZigZag, subtreeMax);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from dataclasses import dataclass


@dataclass(frozen=True)
class T:
  leftMax: int
  rightMax: int
  subtreeMax: int


class Solution:
  def longestZigZag(self, root: TreeNode | None) -> int:
    def dfs(root: TreeNode | None) -> T:
      if not root:
        return T(-1, -1, -1)
      left = dfs(root.left)
      right = dfs(root.right)
      leftZigZag = left.rightMax + 1
      rightZigZag = right.leftMax + 1
      subtreeMax = max(leftZigZag, rightZigZag,
                       left.subtreeMax, right.subtreeMax)
      return T(leftZigZag, rightZigZag, subtreeMax)

    return dfs(root).subtreeMax