( “树” 之 DFS) 687. 最长同值路径 ——【Leetcode每日一题】

蔚落 2024-03-23 12:56 64阅读 0赞

### 687. 最长同值路径 ###

给定一个二叉树的 `root` ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。

**两个节点之间的路径长度** 由它们之间的边数表示。

##### 示例 1: #####

![在这里插入图片描述][23ecca1290e14b578a507c8b9a4ad6f7.png]

> 输入：root = \[5,4,5,1,1,5\]  
> 输出：2

##### 示例 2: #####

![在这里插入图片描述][e0b3d52be3f845d18d639ac2f3bdf226.png]

> 输入：root = \[1,4,5,4,4,5\]  
> 输出：2

**提示:**

*  树的节点数的范围是  \[ 0 , 1 0 4 \] \[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)的空间。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[23ecca1290e14b578a507c8b9a4ad6f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/8eb28d47806c4791b0f406d9caa6cbee.png
[e0b3d52be3f845d18d639ac2f3bdf226.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/617b36bc4ad44e509474f29b95735fe8.png
[Link 1]: https://leetcode.cn/problems/longest-univalue-path/
[leetCode]: http://t.csdn.cn/kQLJO