Leetcode daily # 19.04.2023

[1372. Longest ZigZag Path in a Binary Tree]

19.04.2023

1372. Longest ZigZag Path in a Binary Tree medium

fun longestZigZag(root: TreeNode?): Int {
    var max = 0
    fun dfs(n: TreeNode?, len: Int, dir: Int) {
        max = maxOf(max, len)
        if (n == null) return@dfs
        when (dir) {
            0 -> {
                dfs(n?.left, 0, -1)
                dfs(n?.right, 0, 1)
            }
            1 -> {
                dfs(n?.left, len + 1, -1)
                dfs(n?.right, 0, 1)
            }
            -1 -> {
                dfs(n?.right, len + 1, 1)
                dfs(n?.left, 0, -1)
            }
        }
    }
    dfs(root, 0, 0)
    return max
}

blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/185

Intuition

Search all the possibilities with DFS

Approach

Compute the max as you go

Complexity

• Time complexity:
  O(nlog2(n)), for each level of height we traverse the full tree

• Space complexity:
  O(log2(n))