Longest Zigzag Path in a Tree

medium tree dfs

Problem

A zigzag path repeatedly alternates direction: left, right, left, right (or starting with right). Return the length (in edges) of the longest such path anywhere in the tree. DFS each node returning two values: the longest zigzag continuing left, and the longest continuing right.

Inputtree = [1, _, 1, 1, 1, _, 1, _, 1, 1, _, 1]

Output3

A right-left-right-left chain through the tree.

tree (level-order)

def longest_zigzag(root):
    best = 0
    def dfs(n):
        nonlocal best
        if not n: return (-1, -1)
        ll, lr = dfs(n.left)
        rl, rr = dfs(n.right)
        left, right = lr + 1, rl + 1
        if left > best: best = left
        if right > best: best = right
        return (left, right)
    dfs(root)
    return best

function longestZigzag(root) {
  let best = 0;
  function dfs(n) {
    if (!n) return [-1, -1];
    const [ll, lr] = dfs(n.left);
    const [rl, rr] = dfs(n.right);
    const left = lr + 1, right = rl + 1;
    if (left > best) best = left;
    if (right > best) best = right;
    return [left, right];
  }
  dfs(root);
  return best;
}

class Solution {
    int best;
    public int longestZigzag(TreeNode root) {
        best = 0;
        dfs(root);
        return best;
    }
    private int[] dfs(TreeNode n) {
        if (n == null) return new int[]{ -1, -1 };
        int[] L = dfs(n.left);
        int[] R = dfs(n.right);
        int left = L[1] + 1, right = R[0] + 1;
        if (left > best) best = left;
        if (right > best) best = right;
        return new int[]{ left, right };
    }
}

int best_;
pair<int,int> dfs(TreeNode* n) {
    if (!n) return {-1, -1};
    auto [ll, lr] = dfs(n->left);
    auto [rl, rr] = dfs(n->right);
    int left = lr + 1, right = rl + 1;
    if (left > best_) best_ = left;
    if (right > best_) best_ = right;
    return {left, right};
}
int longestZigzag(TreeNode* root) {
    best_ = 0;
    dfs(root);
    return best_;
}

Time: O(n) Space: O(h)