题目描述
这是 LeetCode 上的 687. 最长同值路径 ,难度为 中等。
Tag : 「二叉树」、「DFS」、「递归」
给定一个二叉树的 root
,返回 最长的路径的长度 ,这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
【687. 最长同值路径 : 简单递归运用题】两个节点之间的路径长度 由它们之间的边数表示。
示例 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)$
No.687
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSou... 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
本文由mdnice多平台发布
推荐阅读
- 从 VLAN 到 IPVLAN: 聊聊虚拟网络设备及其在云原生中的应用
- 云原生时代下,微服务体系与 Serverless 架构的发展、治理与融合
- 内网穿透|frp实现内网穿透
- Spring|Spring-IOC配置-依赖注入
- 一起学Rust|【一起学Rust | 基础篇】rust函数与流程控制详解
- rust|【Rust 笔记】15-字符串与文本(上)
- PHP|分享75个商务商城PHP源码,总有一款适合你
- rm ,rm -rf , rm -f,rm -r 以及rm 命令的其他参数命令
- 笔记|高中毕业,经过半年培训后成功拿到了美团的offer