路径(medium)"/>
[dfs]leetocde687:最长同值路径(medium)
题目:
题解:
- 解题思路类似124. 二叉树中的最大路径和,dfs 求树的最大深度,然后顺便更新同值路径,不同的是若 root 与左右子树中节点值不相同时,需要更新深度为 0,表示重新冲左子树或右子树开始计算深度,然后更新 res,返回树的最大深度。
代码如下:
class Solution {
public:int res=0;int longestUnivaluePath(TreeNode* root) {dfs(root);return res;}// dfs的返回值为树的最大深度int dfs(TreeNode* root){if(!root)return 0;// 递归计算左右子树的深度int l=dfs(root->left),r=dfs(root->right);// 左子树存在,但根节点与左子树的根节点不相等,则需要重新计算深度了,这样从左子树开始的深度为0开始计算if(l>0&&root->val!=root->left->val)l=0;// 右子树同理if(r>0&&root->val!=root->right->val)r=0;res=max(res,l+r);// 返回树的最大深度return max(l,r)+1;}
};
更多推荐
[dfs]leetocde687:最长同值路径(medium)
发布评论