Java recursion failed 2 cases, anyone can help?


  • 1
    B
    public int longestConsecutive(TreeNode root) {
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        int left = 0, right = 0;
        if(root.left != null){
            if(root.val + 1 == root.left.val)
                left = longestConsecutive(root.left) + 1;
            else
                left = longestConsecutive(root.left);
        }
        if(root.right != null){
            if(root.val + 1 == root.right.val)
                right = longestConsecutive(root.right) + 1;
            else 
                right = longestConsecutive(root.right);
        }
        return Math.max(right, left);
    }
    

    I can't find out where is the problem...


  • 0
    S

    Actually I got the almost same idea as yours..


  • 4
    J

    The logic left = longestConsecutive(root.left) + 1; is wrong. The definition of the recursive function is returning max consecutive value of the whole tree, so if max value in root.left does not include root.left, this logic will connect those looking like consecutive. This example can help you understand [1,2,null,1,null,1,2].

    Based on your code, I modified few parts, where I make the definition to be max value locally unless current node is root.

    private int max = 0;
    private TreeNode rt = null;
    public int longestConsecutive(TreeNode root) {
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        if(rt == null)  rt = root;
        int left = 0, right = 0;
        if(root.left != null){
            if(root.val + 1 == root.left.val)
                left = longestConsecutive(root.left) + 1;
            else{
                left = 1;
                longestConsecutive(root.left);
            }
        }
        if(root.right != null){
            if(root.val + 1 == root.right.val)
                right = longestConsecutive(root.right) + 1;
            else{
                right = 1;
                longestConsecutive(root.right);
            }
        }
        max = Math.max(max, Math.max(right, left));
        return rt == root ? max : Math.max(right, left);
    }

  • 0
    B

    Thank you!I got almost same code and your answer really help me out!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.