687. Longest Univalue Path

LeetCode
, ,

今天的题目是687. Longest Univalue Path。

还是比较简单的一道题目，但是太久没做题了，敲代码有点生疏。。。

首先分析一下题目，有几个点需要注意一下：

  • 它要的路径长度，而不是节点数。当然这两个问题非常容易转换，排除掉空树后，节点数减 1 就是路径长度。
  • 这个路径不一定是向下的，也就是说，这条路径是可以从左子树沿着根节点到右子树的。
  • 这条路径可以不经过根节点

应该很容易就可以发现，对于一棵树来说，最长同值路径只可能是以下几种情况：

  • 在左子树中
  • 在右子树中
  • 经过根节点

前两个很容易解决，因为可以用递归的思想，假设当前函数已经可以求出这个长度了，然后递归调用即可。
但是经过根节点的情况就比较复杂了。但是可能的情况也是可以穷举出来的：

  • 最长同值路径只包含左子树和根节点 (root->val == root->left->val)
  • 最长同值路径只包含右子树和根节点 (root->val == root->right->val)
  • 最长同值路径包含左、右子树和根节点 (root->val == root->left->val && root->val == root->right->val)

看上去只需要递归求解左右子树的最长同值路径，然后通过简单的判断
，并对所有情况的路径长度求max即可，但是这又涉及到另一个坑点了：

1
2
3
4
5
    4
   /
  4
 / \
4   4

对于上面这棵树来说，它的最长同值路径是2，而不是3。

而且上面提到的做法也无法解决到最开始提到的第三个坑。

这里采用的做法是在递归求解一棵树的最长同值路径的同时，求解
它经过根节点的、向下的的最长同值路径。

有了这个新的附加条件，我们就可以通过简单的判断来计算经过根节点时最长同值路径的长度。

下面是实现代码（实现上，我们其实求的是路径中节点的个数，然后在最后返回时减一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int longestUnivaluePath(TreeNode* root) {
if (root == nullptr) return 0;
    auto res = helper(root);
    return res.first - 1;
}
pair<int, int> helper(TreeNode *root) {
    if (!root) return make_pair(0, 0);
    auto left = helper(root->left);
    auto right = helper(root->right);
    int lup = 0, rlup = 1;
    
    if (root->left && root->left->val == root->val) {
        lup += left.second;
        rlup = max(rlup, left.second + 1);
    }
    if (root->right && root->right->val  == root->val) {
        lup += right.second;
        rlup = max(rlup, right.second + 1);
    }
    lup += 1;
    lup = max(lup, left.first);
    lup = max(lup, right.first);
    
    return make_pair(lup, rlup);
}