Leetcode687.最长同值路径

1.题目

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

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

示例 1:

输入:

              5
             / \
            4   5
           / \   \
          1   1   5

输出:

2

示例 2:

输入:

              1
             / \
            4   5
           / \   \
          4   4   5

输出:

2

2.题解

使用递归求解,首先我使用的是普通的无脑递归,递归函数的意义为每个以当前节点为根的最长路径,然后返回时判断是否进行加1操作,但是这种解法在一些特殊情况是行不通的

正确的方法是使用一个arrLength的递归函数,表示以当前节点为根,返回最长箭头,箭头是指左右两个子树中的最长路径,这个过程不断的来更新最小值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max;//在递归中一直维护这个最大值
    public int longestUnivaluePath(TreeNode root) {
        max = 0;
        arrLength(root);
        return max;
    }
    //返回每个节点的最长箭头,并更新max
    public int arrLength(TreeNode root){
        if(root == null)    return 0;
        int left = arrLength(root.left);
        int right = arrLength(root.right);
        int leftLength = 0,rightLength = 0;
        if(root.left != null && root.val == root.left.val){
            leftLength = leftLength + left + 1;
        }
        if(root.right != null && root.val == root.right.val){
            rightLength = rightLength + right + 1;
        }
        max = Math.max(max,leftLength+rightLength);
        return Math.max(leftLength,rightLength);
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode687最长同值路径md