96 lines
1.7 KiB
Markdown
96 lines
1.7 KiB
Markdown
|
## 每日一题 - longest-univalue-path
|
|||
|
|
|
|||
|
|
### 信息卡片
|
|||
|
|
|
|||
|
|
- 时间：2019-07-04
|
|||
|
|
- 题目链接：https://leetcode.com/problems/longest-univalue-path/
|
|||
|
|
- tag：`recursive` `tree`
|
|||
|
|
|
|||
|
|
### 题目描述
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
|
|||
|
|
|
|||
|
|
The length of path between two nodes is represented by the number of edges between them.
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
Example 1:
|
|||
|
|
|
|||
|
|
Input:
|
|||
|
|
|
|||
|
|
5
|
|||
|
|
/ \
|
|||
|
|
4 5
|
|||
|
|
/ \ \
|
|||
|
|
1 1 5
|
|||
|
|
Output: 2
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
Example 2:
|
|||
|
|
|
|||
|
|
Input:
|
|||
|
|
|
|||
|
|
1
|
|||
|
|
/ \
|
|||
|
|
4 5
|
|||
|
|
/ \ \
|
|||
|
|
4 4 5
|
|||
|
|
Output: 2
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 参考答案
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
/*
|
|||
|
|
* @lc app=leetcode id=687 lang=javascript
|
|||
|
|
*
|
|||
|
|
* [687] Longest Univalue Path
|
|||
|
|
*/
|
|||
|
|
|
|||
|
|
// 返回经过root的且只能取左右一个节点的路径长度
|
|||
|
|
function helper(node, res) {
|
|||
|
|
if (node === null) return 0;
|
|||
|
|
const l = helper(node.left, res);
|
|||
|
|
const r = helper(node.right, res);
|
|||
|
|
let lcnt = 0;
|
|||
|
|
let rcnt = 0;
|
|||
|
|
if (node.left && node.val === node.left.val) lcnt = lcnt + l + 1;
|
|||
|
|
if (node.right && node.val === node.right.val) rcnt = rcnt + r + 1;
|
|||
|
|
|
|||
|
|
res.max = Math.max(res.max, lcnt + rcnt);
|
|||
|
|
|
|||
|
|
return Math.max(lcnt, rcnt);
|
|||
|
|
}
|
|||
|
|
/**
|
|||
|
|
* Definition for a binary tree node.
|
|||
|
|
* function TreeNode(val) {
|
|||
|
|
* this.val = val;
|
|||
|
|
* this.left = this.right = null;
|
|||
|
|
* }
|
|||
|
|
*/
|
|||
|
|
/**
|
|||
|
|
* @param {TreeNode} root
|
|||
|
|
* @return {number}
|
|||
|
|
*/
|
|||
|
|
var longestUnivaluePath = function(root) {
|
|||
|
|
const res = {
|
|||
|
|
max: 0
|
|||
|
|
};
|
|||
|
|
helper(root, res);
|
|||
|
|
return res.max;
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 其他优秀解答
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
暂无
|
|||
|
|
```
|