[数据结构与算法]LeetCode 687 Longest Univalue Path (dfs dp 推荐)

Given the?root?of a binary tree, return?the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root.

The length of the path?between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [5,4,5,1,1,5]
Output: 2

Example 2:

Input: root = [1,4,5,4,4,5]
Output: 2

Constraints:

• The number of nodes in the tree is in the range?[0, 104].
• -1000 <= Node.val <= 1000
• The depth of the tree will not exceed?1000.

题目链接：https://leetcode.com/problems/longest-univalue-path/

题目大意：求值相同的最大路径的边长

题目分析：与求路径值和的最大值那题思路类似，对当前点，分别求向左和向右所能延伸的最长距离，如果下一个节点与当前点的值不同，则以下一节点值为基准继续向后比较，返回值取向左向右中较大的是因为当前点作为上一个节点的子节点，只能选择一个方向延伸

?1ms，时间击败100%

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    int ans = 0;
    
    private int dfs(TreeNode root, int curVal) {
        if (root.left == null && root.right == null) {
            return 0;
        }
        int maxLeft = 0;
        if (root.left != null) {
            if (root.left.val == curVal) {
                maxLeft = 1 + dfs(root.left, curVal);
            } else {
                dfs(root.left, root.left.val);
            }
        }
        int maxRight = 0;
        if (root.right != null) {
            if (root.right.val == curVal) {
                maxRight = 1 + dfs(root.right, curVal);
            } else {
                dfs(root.right, root.right.val);
            }
        }
        //System.out.println("curval = " + curVal + " l = " + maxLeft + " r = " + maxRight);
        ans = Math.max(ans, maxLeft + maxRight);
        return Math.max(maxLeft, maxRight);
    }
    
    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root, root.val);
        return ans;
    }
}