687. 最长同值路径
给定一个二叉树的 root
,返回 最长的路径的长度 ,这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度 由它们之间的边数表示。
示例 1:
输入:root = [5,4,5,1,1,5]
输出:2
示例 2:
输入:root = [1,4,5,4,4,5]
输出:2
提示:
- 树的节点数的范围是 [0,104][0, 10^4][0,104]
- -1000 <= Node.val <= 1000
- 树的深度将不超过 1000
思路:DFS
分析:
对任意一个节点,有两种可能,最大路径可能经过该节点,或者不经过该节点
- 最大路径经过该节点时:
- 若该节点为最大路径的根节点
root
时, 路径长度 为左子树的路径长度
加上右子树的路径长度
; - 若节点不是最大路径的根节点时,则最大路径的根节点
root
一定在其父节点上,此时返回其左右子树的路径的最大值
;
- 若该节点为最大路径的根节点
- 最大路径不经过该节点时,返回
0
.
设计:(从下往上判断)
根据上述分析,设计递归函数int dfs(TreeNode root)
- 含义为传入根节点
root
, 返回最大路径经过该节点,但是该节点不是最大路径的根节点,即返回其左右子树的路径的最大值
; - 同时设置全局变量
path
,记录最大路径,在每个节点为根节点时判断更新,即左子树的路径长度
加上右子树的路径长度
; - 在递归函数内部,先通过递归
root
的左右子节点,拿到以root.left
和root.right
为起点的最大路径长度left
和right
,然后以root
节点为最大路径的根节点 ,分别判断左右子树的val
值是否等于root.val
,如果相等则加1
,不等则为0
- 同时更新最大路径
path
。
代码:(Java、C++)
Java
/*** 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 {private int path = 0;public int longestUnivaluePath(TreeNode root) {dfs(root);return path;}public int dfs(TreeNode root){if(root == null) return 0;int left = dfs(root.left);int right = dfs(root.right);int leftPath = root.left != null && root.val == root.left.val ? 1 + left : 0;int rightPath = root.right != null && root.val == root.right.val ? 1 + right : 0;path = Math.max(path, leftPath + rightPath); return Math.max(leftPath, rightPath);}
}
C++
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int path = 0;int longestUnivaluePath(TreeNode* root) {dfs(root);return path;}int dfs(TreeNode* root){if(root == NULL) return 0;int left = dfs(root->left);int right = dfs(root->right);int leftPath = root->left != NULL && root->val == root->left->val ? 1 + left : 0;int rightPath = root->right != NULL && root->val == root->right->val ? 1 + right : 0;path = max(path, leftPath + rightPath); return max(leftPath, rightPath);}
};
运行结果:
复杂度分析:
- 时间复杂度:O(n)O(n)O(n),其中
n
为树的结点数目。 - 空间复杂度:O(n)O(n)O(n)。递归栈最坏情况下需要O(n)O(n)O(n)的空间。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!