陕西网站建设吉林市城市建设档案馆官方网站

题目链接

二叉树中的最长交错路径

题目描述

注意点

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

关键点

• 深度优先遍历的思想
• 因为最长交错路径可能在二叉树中间，所以在深搜的过程中还要传入之前路径的长度和之前路径的方向