目录

题目描述：

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

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

示例 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(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    void getPath(TreeNode* root, int& lh, int & rh, int & res){        // lh indicates height of the path in left subtree with same value         // rh indicates height of the path in right subtree with same value        if(!root){            lh = 0;            rh = 0;        }else{            lh = 0, rh = 0;            int _res = 0;            if(root->left){                int llh = 0, lrh = 0;                getPath(root->left, llh, lrh, res);                if(root->left->val == root->val){                    lh = max(llh, lrh) + 1;                }            }            if(root->right){                int rlh = 0, rrh = 0;                getPath(root->right, rlh, rrh, res);                if(root->right->val == root->val){                    rh = max(rlh, rrh) + 1;                }            }            res = max(lh + rh, res);        }    }        int longestUnivaluePath(TreeNode* root) {        int lh = 0, rh = 0, res = 0;        getPath(root, lh, rh, res);        return res;    }};