【9.2】687. 最长同值路径

路径问题难度排序：LC124–>LC543–>LC687–>LC2246

简单的递归方法，使用sum保存最大的分支路径，使用ret判断是否将最大值更新为两条分支路径之和

    int ret=0;
    int dfs(TreeNode* root) {
        if(!root) return 0;
        int sum=0, curr=0, l=dfs(root->left), r=dfs(root->right);
        if(root->left && root->val==root->left->val) {
            sum = l+1;
            curr += l+1;
        }
        if(root->right && root->val==root->right->val) {
            sum = max(sum, r+1);
            curr += r+1;
        }
        ret = max(curr, sum)>ret?max(curr,sum):ret;
        return sum;
    }
    int longestUnivaluePath(TreeNode* root) {
        int tmp = dfs(root);
        return ret;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19