题目大意：求二叉树中每个节点值都相同的最长路径长度，长度=节点间边数。
分析：dfs。维护全局maxLen，对每个节点求最长路径。经过该节点的最长路径=leftLen+rightLen。LeftGain、RightGain分别为左右子节点的最大贡献值。节点最大贡献值=节点值+max(leftGain,rightGain)，因为贡献值代表该节点左侧路径or右侧路径二选一，选择一条贡献值最大的继续往该节点的父节点贡献。
代码：
/** * 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 maxLen = 0; public: int longestUnivaluePath(TreeNode* root) { dfs(root); return maxLen; } int dfs(TreeNode* root) { if(!root) return 0; int leftLen = dfs(root->left); //求左节点的最长贡献值 int rightLen = dfs(root->right); //求右节点的最长贡献值 int rootLeft = 0,rootRight = 0; //维护root开始的左右分支的最长同值路径长度 if(root->left && root->left->val == root->val) rootLeft += leftLen + 1;; if(root->right && root->right->val == root->val) rootRight += rightLen + 1; maxLen = max(rootLeft + rootRight,maxLen); //更新经过root的最长同值路径 return max(rootLeft,rootRight); //返回节点最长贡献值 } };
