Блог

Пытаюсь решить проблему с кодом, но я застрял на этом вопросе с одним деревом. https://leetcode.com/problems/longest-univalue-path /

Мое решение не работает для приведенного ниже тестового примера, но я попытался его отладить и не смог понять, почему. Когда я просматриваю его, я получаю правильный ответ в своем коде. Надеюсь, кто-нибудь может сказать мне, что я сделал не так. Спасибо, ниже приведен тестовый пример, в котором он терпит неудачу, и мой код на Java

 [5,4,5,4,4,5,3,4,4,null,null,null,4,null,null,4,null,null,4,null,4,4,null,null,4,4]
  

 class Solution {
    int longestPath = 0;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root, root.val);
        
        return longestPath ;
    }
    
        public int dfs(TreeNode root, int value){
        if(root == null) return 0;
        
        int leftPath = dfs(root.left, root.val);
        int rightPath = dfs(root.right, root.val);
        
        longestPath = Math.max(longestPath, leftPath   rightPath);
        
        int val = (root.val == value) ? 1 : 0;
        return Math.max(leftPath, rightPath)   val;
    }
}
  

Выглядит хорошо!

Условие возврата должно быть изменено. Это пройдет:

 class Solution {
    int longestPath = 0;
    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        dfs(root, root.val);

        return longestPath ;
    }

    public int dfs(TreeNode root, int value) {
        if (root == null) {
            return 0;
        }

        int leftPath = dfs(root.left, root.val);
        int rightPath = dfs(root.right, root.val);

        longestPath = Math.max(longestPath, leftPath   rightPath);

        return root.val == value ? 1   Math.max(leftPath, rightPath) : 0;
    }
}