687.Longest Univalue Path

687.Longest Univalue Path

难度:Easy

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.

主要是采用递归。 最大长度是该节点左右子树的最大长度，不会与该节点的父节点及其祖先节点有关。 因此可以以每个节点为根节点，最后求出最长的长度。

/**
 * 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 {
int res=0;
int getPathValue(TreeNode* root)
{
    if(!root) return 0;
    int leftLength= getPathValue(root->left);
    int rightLength= getPathValue(root->right);
    int ansLeft=0;
    int ansRight=0;
    if(root->left && root->left->val == root->val)
        ansLeft+=leftLength+1;
    if(root->right && root->right->val == root->val)
        ansRight+=rightLength+1;
    res=max(res,ansLeft+ansRight);
    return max(ansLeft,ansRight);
}
public:
    int longestUnivaluePath(TreeNode* root) {
        getPathValue(root);
        return res;
    }
};

执行用时 :156 ms, 在所有 C++ 提交中击败了99.77%的用户 内存消耗 :49.6 MB, 在所有 C++ 提交中击败了78.82%的用户