1372. Longest ZigZag Path in a Binary Tree

题目信息

题号:

1372

难度:

Medium

主题:

二叉树、深度优先搜索、路径状态

原题:

LeetCode 1372

重点:

路径可从任意节点开始,移动方向必须左右交替;长度按经过的边数计算

题目重述

给定一棵二叉树。选择任意节点作为起点和首次向左或向右的方向;每走一步后,下一步必须改走相反方向,持续到无法继续。

请返回树中最长之字形路径的边数。单个节点构成长度为 0 的路径。

树中节点数不超过 5 * 10^4,节点值不影响答案。

自建示例

路径可以连续左、右、左交替:

输入:root = [1,2,3,null,4,5,null,6]
输出:3
解释:路径 1 -> 2 -> 4 -> 6 的方向依次为左、右、左,共三条边。

单节点树没有可走的边:

输入:root = [9]
输出:0
解释:只有起始节点。