科特林二叉树中最长的曲折路径

Question

我试图用kotlin中的递归来回答leetcode上二叉树中最长的曲折路径。输入如下所示

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

并表示二叉树。我遇到的问题与递归有关，我当前的代码在访问树中的所有节点后返回 1。但我打算让代码在每个树节点命中后添加 1 并将其添加到该锯齿形总数中。

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

左和右仅表示每个路径侧的相应之字形。我想知道的是，如何在每次递归调用后以println语句的方式添加这些值

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

Answer 1

我无法轻松运行您的代码来验证这一点，但我相信您需要替换它：

traverseDirection(current, "right")
return 1 

有了这个：

return traverseDirection(current, "right") + 1

“左”倾路线也是如此。

此外，我认为只有从根部开始，你的解决方案才能找到最长的之字形。您必须为树中的每个节点运行longestZigZag（）并找到最大值。这将为您提供一个O（n²）复杂度的简单解决方案。