1372.longest-zigzag-path-in-a-binary-tree.md

1372. Longest ZigZag Path in a Binary Tree

Breakdowns

1. How to find the longest leftward or rightward path in a tree?

private fun dfs(root: TreeNode?): Int {
    if (root == null) return 0
    return if (root.left != null) 1 + dfs(root.left) else 0
}

Double Recursion

// Previous direction is right,
...
  \
   root
   /   \
left    \
// Extend the existing zigzag path to the left child, steps = steps + 1
          \
           right
// Or we can start a new zigzag path from the current root, steps = 0

private val LEFT = 1
private val RIGHT = -1
private var longestPath = 0
fun longestZigZag(root: TreeNode?): Int {
    if (root == null) return 0
    dfs(root.left, LEFT, 0)
    dfs(root.right, RIGHT, 0)
    return longestPath
}

/**
 * @param previousDirection: 0 for left, 1 for right
 * @param steps: The total steps before the root.
 */
private fun dfs(root: TreeNode?, previousDirection: Int, steps: Int) {
    if (root == null) return
    longestPath = maxOf(longestPath, steps + 1)

    // Previously go left, then it should go right
    if (previousDirection == LEFT) {
        dfs(root.right, RIGHT, steps + 1)

        // Or we start new zigzag path from left child
        dfs(root.left, LEFT, 0)
    } else {
        dfs(root.left, LEFT, steps + 1)

        // Or we start new zigzag path from right child
        dfs(root.right, RIGHT, 0)
    }
}