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

中文域名的网站百度明星人气榜入口

news 2026/4/7 12:56:57

中文域名的网站,百度明星人气榜入口,中国建设银行甘肃省分行官方网站,国际新闻热点事件题目链接二叉树中的最长交错路径题目描述注意点每棵树最多有 50000 个节点每个节点的值在 [1, 100] 之间起点无需是根节点解答思路要找到最长交错路径，首先想到的是深度优先遍历因为起点无需是根节点，所以对于任意一个节点，其可以…

题目链接

二叉树中的最长交错路径

题目描述

注意点

每棵树最多有 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);}}
}