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
20
21
22
23
24
25
26
27
28
29
class T {
  public int leftMax;
  public int rightMax;
  public int subtreeMax;

  public T(int leftMax, int rightMax, int subtreeMax) {
    this.leftMax = leftMax;
    this.rightMax = rightMax;
    this.subtreeMax = subtreeMax;
  }
}

class Solution {
  public int longestZigZag(TreeNode root) {
    return dfs(root).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
class T:
  def __init__(self, leftMax: int, rightMax: int, subtreeMax: int):
    self.leftMax = leftMax
    self.rightMax = rightMax
    self.subtreeMax = subtreeMax


class Solution:
  def longestZigZag(self, root: Optional[TreeNode]) -> int:
    def dfs(root: Optional[TreeNode]) -> 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