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

1. Use recursion:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     int longestUnivaluePath(TreeNode* root) {
  13.         int result = 0;
  15.         arrowLength(root, result);
  17.         return result;
  18.     }
  20. private:
  21.     int arrowLength(TreeNode* root, int& result){
  22.         if(!root) return 0;
  24.         int l_path = arrowLength(root->left, result);
  25.         int r_path = arrowLength(root->right, result);
  27.         int arrowLeft = 0, arrowRight = 0;
  29.         if(root->left && root->left->val == root->val)
  30.             arrowLeft =  arrowLeft + l_path + 1;
  31.         if(root->right && root->right->val == root->val)
  32.             arrowRight =  arrowRight + r_path + 1;
  34.         result = max(result, arrowLeft + arrowRight);
  36.         return max(arrowLeft, arrowRight);
  37.     }
  38. };