最长同值路径(备忘)
(1)设置返回以root为根节点的树的最长同值路径的长度。
(2)递归,以每一个节点为根节点进行(1),并取其中的最大长度。
需注意的是,在(1)操作中,根节点是特殊的;具体的说:若同值路径存在,只有根节点的左儿子
和右儿子可以被同时接入路径;对于路径中其他节点,最多只有一个子节点被接入路径。
代码详细注释
C++代码
class Solution {
public:
int ans = 0;
int longestUnivaluePath(TreeNode* root) {
arrowLength(root);
return ans;
}
int arrowLength(TreeNode* root){//arrowLength返回以root为根节点的单侧最大同值路径的长度
//官方答案的思路非常巧妙 可以学习一下
if(!root) return 0;//
int left = arrowLength(root->left);//left存储以root的左孩子为根节点的最大同值路径的长度
int right = arrowLength(root->right);//存储以root的右孩子为根节点的最大同值路径的长度
int arrowLeft = 0, arrowRight = 0;
if(root->left && root->left->val == root->val){//若root的左孩子不为空且左孩子值与root值相等
arrowLeft += left + 1;
}
if(root->right && root->right->val == root->val){//若root的右孩子不为空且右孩子值与root值相等
arrowRight += right + 1;
}
ans = max(ans, arrowLeft + arrowRight);//ans存放步骤(2)的结果
return max(arrowLeft, arrowRight);//保证路径不分叉且取到最大
}