C语言重构【687】最长同值路径

悠悠 2022-12-19 09:20 132阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
    
    注意：两个节点之间的路径长度由它们之间的边数表示。
    
    示例 1:
    
    输入:
    
                  5
                 / \
                4   5
               / \   \
              1   1   5
    输出:
    
    2
    示例 2:
    
    输入:
    
                  1
                 / \
                4   5
               / \   \
              4   4   5
    输出:
    
    2
    注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

#### 方案： ####

/** * 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 longestUnivaluePath(TreeNode* root) { 
            int ans = 0;
            findUnivalPath(root, ans);
            return ans;
        }
        int findUnivalPath(TreeNode* node,int &ans){ 
            if (node == nullptr) return 0;
    
            int left = findUnivalPath(node->left, ans);
            int right = findUnivalPath(node->right, ans);
    
            left = (node->left != nullptr && node->val == node->left->val) ? left + 1 : 0;
            right = (node->right != nullptr && node->val == node->right->val) ? right + 1 : 0;
    
            ans = max(ans, left + right);
            return max(left, right);
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode