687.Longest Univalue Path¶

687.Longest Univalue Path¶

Tags: Easy Recursion

Links: https://leetcode.com/problems/longest-univalue-path/

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:

Output: 2

Example 2:

Input:

Output: 2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int res = INT_MIN;
        DFS(root, res);

        return res == INT_MIN ? 0 : res;
    }
    //代表以当前根节点为起始的最长路径
    int DFS(TreeNode *root, int &res)
    {
        //空节点直接返回或叶节点直接返回
        if (!root || (!root -> left && !root -> right)) return 0; 

        int left = DFS(root -> left, res);
        int right = DFS(root -> right, res); 

        int cnt = 0;
        int maxDepth = 0;
        if (root -> left && root -> val == root -> left -> val) {
            cnt += left + 1;
            maxDepth = max(maxDepth, 1 + left);
        }
        if (root -> right && root -> val == root -> right -> val) {
            cnt += right + 1;
            maxDepth = max(maxDepth, 1 + right);
        }
        res = max(res, cnt);

        return maxDepth;
    }
};

更加精简的写法：

首先还是先判断root是否为空，是的话返回0。然后对左右子节点分别调用当前函数，取其中较大值保存到变量sub中，表示左右子树中最长的相同值路径，然后就是要跟当前树的最长相同值路径比较，计算方法是对左右子结点调用一个helper函数，并把当前结点值传进去，把返回值加起来和sub比较，取较大值返回。helper的返回值意义表示的是以当前结点的父结点为路径终点的最大相同值路径长度，在helper函数里，若当前结点为空，或者当前节点值不等于父结点值的话，返回0。否则结返回对左右子结点分别调用helper递归函数中的较大值加1，这种写法跟求树的最大深度很像

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!root) return 0;
        int sub = max(longestUnivaluePath(root -> left), longestUnivaluePath(root -> right));

        return max(sub, helper(root -> left, root -> val) + helper(root -> right, root -> val));
    }
    //helper代表以root为重点的最长路径
    int helper(TreeNode *root, int num)
    {
        if (!root || root -> val != num) return 0;
        return 1 + max(helper(root -> left, root -> val), helper(root -> right, root -> val));
    }

};