Leetcode 1372:二叉树中的最长交错路径(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1372:二叉树中的最长交错路径(超详细的解法!!!)

in leetcode with 0 comment

给你一棵以 root 为根的二叉树,二叉树中的交错路径定义如下:

交错路径的长度定义为:访问过的节点数目 - 1(单个节点的路径长度为 0 )。

请你返回给定树中最长 交错路径 的长度。

示例 1:

输入:root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
输出:3
解释:蓝色节点为树中最长交错路径(右 -> 左 -> 右)。

示例 2:

输入:root = [1,1,1,null,1,null,null,1,1,null,1]
输出:4
解释:蓝色节点为树中最长交错路径(左 -> 右 -> 左 -> 右)。

示例 3:

输入:root = [1]
输出:0 

提示:

解题思路

树型问题首先思考递归解,关于树中不确定起点的问题之前处理过Leetcode 1120:子树的最大平均值。定义函数$f(root)$返回以root为根向左走和向右走的结果

class Solution:
    def longestZigZag(self, root: TreeNode) -> int:
        res = 0
        def dfs(root):
            nonlocal res
            if not root: return [-1, -1]
            left, right = dfs(root.left), dfs(root.right)
            res = max(res, left[1] + 1, right[0] + 1)
            return [left[1] + 1, right[0] + 1]
        
        dfs(root)
        return res

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses