[算法练习] Leetcode 687 最长同值路径

题目

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:

          5
         / \
        4   5
       / \   \
      1   1   5

输出: 2

示例 2:
输入:

          1
         / \
        4   5
       / \   \
      4   4   5

输出: 2

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

解题思路

我们定义函数longestUnivalue返回左右两边其中最大的路径长度，此时我们有四种情况考虑

• root.left == root == root.right

• root.left == root

• root.right == root

• root.left ！= root != root.right

• 对于第一种情况此时左右孩子和根相同，需要更新的最大长度res=max(res,l+r+2)，并且返回max(l,r)+1

• 对于第二种情况，此时左孩子和根相同，需要更新最大长度res=max(res,l+1)，并且返回l+1

• 对于第三种情况，此时右孩子和根相同，需要更新最大长度res=max(res,r+1)，并且返回r+1。

• 对于第四种情况，此时只需返回0即可。

代码实现

public int visitTreeLongestPath(Node node) {
       if (node == null) {
           return 0;
       }

       int left = visitTreeLongestPath(node.left);
       int right = visitTreeLongestPath(node.right);

       if (node.left != null && node.left.value == node.value &&
               node.right != null && node.right.value == node.value) {
           Math.max(currentMax, left + right + 2);
           return  Math.max(left, right) + 1;
       }

       if (node.left != null && node.left.value == node.value) {
           int value = left + 1;
           Math.max(currentMax, value);
           return value;
       }

       if (node.right != null && node.right.value == node.value) {
           int value = right + 1;
           Math.max(currentMax, value);
           return value;
       }

       return 0;
   }

类似问题

• Leetcode 124：二叉树中的最大路径和（超详细的解法！！！）
• Leetcode 543：二叉树的直径（超详细的解法！！！）

参考: https://blog.csdn.net/qq_17550379/article/details/87380945