1372. Longest ZigZag Path in a Binary Tree¶
题目信息¶
- 题号:
1372
- 难度:
Medium
- 主题:
二叉树、深度优先搜索、路径状态
- 原题:
- 重点:
路径可从任意节点开始,移动方向必须左右交替;长度按经过的边数计算
题目重述¶
给定一棵二叉树。选择任意节点作为起点和首次向左或向右的方向;每走一步后,下一步必须改走相反方向,持续到无法继续。
请返回树中最长之字形路径的边数。单个节点构成长度为 0 的路径。
树中节点数不超过 5 * 10^4,节点值不影响答案。
自建示例¶
路径可以连续左、右、左交替:
输入:root = [1,2,3,null,4,5,null,6]
输出:3
解释:路径 1 -> 2 -> 4 -> 6 的方向依次为左、右、左,共三条边。
单节点树没有可走的边:
输入:root = [9]
输出:0
解释:只有起始节点。