共计 1607 个字符，预计需要花费 5 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 687. 最长同值门路 ，难度为 中等。
Tag :「二叉树」、「DFS」、「递归」
给定一个二叉树的 root，返回 最长的门路的长度，这个门路中的 每个节点具备雷同值。这条门路能够通过也能够不通过根节点。
两个节点之间的门路长度 由它们之间的边数示意。
示例 1:
输出：root = [5,4,5,1,1,5]
输入：2示例 2:
输出：root = [1,4,5,4,4,5]
输入：2提醒:
- 树的节点数的范畴是 $[0, 10^4] $
- $-1000 <= Node.val <= 1000$
- 树的深度将不超过
1000
递归
设计递归函数 int dfs(TreeNode root)，含意为传入根节点 root，返回以该节点为终点，往下走同值门路所能通过的最大门路长度（即不能同时往左右节点走），同时应用全局变量 max 记录答案门路所能通过最大门路长度。
在递归函数外部，先通过递归 root 的左右子节点，拿到以 root.left 和 root.right 为终点的最大门路长度 l 和 r，而后依据以后节点值和左右子节点值的相等关系来更新 ans，同时用 cur 保护「以以后节点 root 为指标门路中深度最小（地位最高）节点时」所通过的最大门路长度。
Java 代码：
class Solution {
int max = 0;
public int longestUnivaluePath(TreeNode root) {dfs(root);
return max;
}
int dfs(TreeNode root) {if (root == null) return 0;
int ans = 0, cur = 0, l = dfs(root.left), r = dfs(root.right);
if (root.left != null && root.left.val == root.val) {ans = l + 1; cur += l + 1;}
if (root.right != null && root.right.val == root.val) {ans = Math.max(ans, r + 1); cur += r + 1;
}
max = Math.max(max, cur);
return ans;
}
}TypeScript 代码：
let max = 0;
function longestUnivaluePath(root: TreeNode | null): number {
max = 0
dfs(root)
return max
};
function dfs(root: TreeNode | null): number {if (root == null) return 0
let ans = 0, cur = 0, l = dfs(root.left), r = dfs(root.right)
if (root.left != null && root.left.val == root.val) {ans = l + 1; cur += l + 1}
if (root.right != null && root.right.val == root.val) {ans = Math.max(ans, r + 1); cur += r + 1
}
max = Math.max(max, cur)
return ans
}- 工夫复杂度：$O(n)$
- 空间复杂度：疏忽递归带来的额定空间开销，复杂度为 $O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.687 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
