LeetCode动画 | 687. 最长同值路径

今天分享一个LeetCode题，题号是687，题目是最长同值路径，题目标签是树和递归，题目难度是简单。。。

这竟然是个简单题，也是六的很。

题目描述

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

          5
         / \
        4   5
       / \   \
      1   1   5

输出:

2

示例 2:

输入:

          1
         / \
        4   5
       / \   \
      4   4   5

输出:

2

注意: 给定的二叉树不超过10000个结点。树的高度不超过1000。

解题

题目标签只有树和递归，树的递归无非就是前、中、后序遍历和层序遍历，那此题适合树的哪种遍历方式呢？

重点在递归，要知道递归是将原问题分解一个个可以解决的小问题，那就找找可以解决的小问题在哪里。如下图：

可解决的小问题

假设节点A和节点C是可以解决问题的小问题，都标记为1。

如果节点A和节点B同值，就获取节点A的标记，设为临时标记a，a=节点A的标记，如果不同值则将a=0；

如果节点C和节点B同值，也获取节点C的标记，设为临时标记c，c=节点C的标记，如果不同值则将c=0；

接着可以计算以节点B为顶点的子树的最长同值路径 a+c。

节点B标记哪个数有三种情况：

若节点B和左右子节点都不同值则被标记为1；

若节点B和左右子节点中的一个节点同值，则被标记为同值的子节点的标记值+1；

若节点B和左右子节点都同值，则被标记为俩子节点中最大的标记值+1；

然后依次解决一个一个子问题，直到原问题被解决，可以获取这棵树的最长同值路径。

后序遍历是先解决两个子节点再解决子节点的父节点，动画如下：

动画：后序遍历

知道了用后序遍历可以解决一个一个小问题，从叶子节点开始，到以非叶子节点为顶点的子树，保存这个子树的最长同值路径，通过后序遍历依次解决以所有非叶子节点为顶点的小问题，直到根节点。看下面动画：

动画：使用递归解此题

Code

private int count;

public int longestUnivaluePath(TreeNode root) {
    count = 0;
    // 采用后序遍历
    traverse(root);
    return count;
}

private int traverse(TreeNode node) {
    if (node == null) return 0;
    int left = traverse(node.left);
    int right = traverse(node.right);
    // 合并子问题
    int l = 0, r = 0;
    if (node.left != null && node.left.val == node.val) l += left;
    if (node.right != null && node.right.val == node.val) r += right;
    count = count > l + r ? count : l + r;
    return l > r ? l + 1 : r + 1;
}

做完之后，这题确实是个简单题嗷。