I'm attempting to answer longest zigzag path in a binary tree on leetcode with recursion in kotlin. The input looks like this

[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1] 

and represents a binary tree. The problem I'm having is related to the recursion, the current code I have returns 1 after visiting all nodes in the tree. But I intended for the code to add 1 after each tree node is hit and add it to that zigzags total count.

left += traverseDirection(root?.left, "left") right += traverseDirection(root?.right, "right") 

left and right just represent the corresponding zigzag for each path side. What I want to know is how to add to these values after each recursive call in the way my println statements are doing it

/** * Example: * var ti = TreeNode(5) * var v = ti.`val` * Definition for a binary tree node. * class TreeNode(var `val`: Int) { * var left: TreeNode? = null * var right: TreeNode? = null * } */ class Solution { fun longestZigZag(root: TreeNode?): Int { var left: Int = 0 var right: Int = 0 left += traverseDirection(root?.left, "left") right += traverseDirection(root?.right, "right") return maxOf(left, right) } fun traverseDirection(root: TreeNode?, direction: String): Int { if (direction == "left" && root?.left == null){ return 0 } if (direction == "right" && root?.right == null){ return 0 } var current = root if (direction == "left"){ current = root?.left traverseDirection(current, "right") println("add 1") return 1 } if (direction == "right"){ current = root?.right traverseDirection(current, "left") println("add 1") return 1 } return 0 } } 
1

1 Answer

I can't easily run your code to verify this, but I believe you need to replace this:

traverseDirection(current, "right") return 1 

With this:

return traverseDirection(current, "right") + 1 

And the same with the "left" line.

Also, I think your solution will find the longest zigzag only if it starts at the root. You would have to run longestZigZag() for each node in the tree and find the maximum. That would give you a naive solution with O(n²) complexity.

ncG1vNJzZmirpJawrLvVnqmfpJ%2Bse6S7zGiorp2jqbawutJobmtsZ26Bc4SOpKatpJmjeq27zaCcrKxdr7aoxsCgZKmZpJ16qrqMm6CnmaKuerW%2BxJ4%3D