一、題目描述

給定一個二叉樹，找到最長的路徑，這個路徑中的每個節點具有相同值。 這條路徑可以經過也可以不經過根節點。

注意：兩個節點之間的路徑長度由它們之間的邊數表示。

二、示例

示例 1:

輸入:

5/ \4 5/ \ \1 1 5

輸出:

2

示例 2:

輸入:

1/ \4 5/ \ \4 4 5

輸出:

2

注意: 給定的二叉樹不超過10000個結點。 樹的高度不超過1000。

三、分析

每個子樹的最長同值路徑為：其左子樹的最長同值路徑＋右子樹的最長同值路徑。
遞歸求解。對于某個節點，判斷其左孩子的值是否與其相等，相等則left等于1+左子樹的最長同值路徑，否則直接處理左子樹，對右子樹做相同計算。計算left、right之和，更新最大值，返回left和right的最大值。

四、實現

/*** 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) {if(root == NULL)return 0;int max = 0;dfs(root, max);return max;}int dfs(TreeNode* root, int &max){int left = 0;int right = 0;if(root->left != NULL && root->val == root->left->val){left = 1 + dfs(root->left, max);}else if(root->left != NULL){dfs(root->left, max);}if(root->right != NULL && root->val == root->right->val){right = 1 + dfs(root->right, max);}else if(root->right != NULL){dfs(root->right, max);}if(left + right > max)max = left + right;return left > right ? left : right ; } };

總結

以上是生活随笔為你收集整理的【LeetCode】687. 最长同值路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。