当前位置：首页 > news >正文

二叉树中的最长交错路径

news 2025/8/8 10:09:57

题目链接

二叉树中的最长交错路径

题目描述

注意点

每棵树最多有 50000 个节点
每个节点的值在 [1, 100] 之间
起点无需是根节点

解答思路

要找到最长交错路径，首先想到的是深度优先遍历
因为起点无需是根节点，所以对于任意一个节点，其可以选择两条路径（对应其左右子树）：
- 如果到达子树的方向与父节点到达该节点的方向相反，则到达该子树是交错路径，可以根据到达该节点的长度len计算
- 如果到达子树的方向与父节点到达该节点的方向相同，则如果要到达该子树，只能将当前节点视作起点，之前到达该节点的长度不做贡献，长度重置为1

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int res = 0;public int longestZigZag(TreeNode root) {if (root == null) {return 0;}dfs(root.left, true, 1);dfs(root.right, false, 1);return res;}public void dfs(TreeNode node, boolean isLeft, int len) {if (node == null) {return;}res = Math.max(res, len);if (isLeft) {dfs(node.right, false, len + 1);dfs(node.left, true, 1);} else {dfs(node.right, false, 1);dfs(node.left, true, len + 1);}}
}