Kotlin递归求解LeetCode二叉树最长ZigZag路径返回值异常问题

基本信息 #

• 实现语言：Kotlin
• 题目：LeetCode 二叉树最长ZigZag路径（longest zigzag path in binary tree）
• 测试输入：[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]，为二叉树的层序遍历表示数组

问题描述 #

当前编写的递归代码遍历完整棵树后仅返回结果1，不符合预期。预期逻辑为：每访问到ZigZag路径上的一个节点就将计数加1，累加到对应ZigZag路径的总长度。
代码中left、right变量分别代表从根节点左、右子节点起始的ZigZag路径长度，对应递归调用代码片段如下：

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

需要修改递归调用逻辑，实现和代码中println("add 1")逻辑一致的路径长度累加效果。

当前完整实现代码 #

/**
 * 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
    }
}

内容的提问来源于stack exchange，提问作者codedixon