本文共 1146 字，大约阅读时间需要 3 分钟。

给你一棵以 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

提示：

• 每棵树最多有 50000 个节点。
• 每个节点的值在 [1, 100] 之间。

解题思路

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

• $f(node)=[f(node.left)[1]+1,f(node.right)[0]+1]$

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

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

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/104759802 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！