Why this code cannot pass test53


  • 0
    S

    public class Solution {

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

    }


  • 0
    O

    I used to get exactly the same fail and coded exactly the same as you. You can find the bug by test case:

    1 -> 2 -> 3 -> 5 -> 6

    where 1 is the tree root. It's better you find it by yourself.

    Below is the code I cleaned the bug.

    public class Solution {
        public int longestConsecutive(TreeNode root) {
            int[] gMax = new int[1];
            lc(root, gMax);
            return gMax[0];
        }
        // strictly define lc(root, gMax) calculating L.C. starting WITH root
        public int lc(TreeNode root, int[] gMax) {  
            if (root == null) return 0;
            int ans = 1, l = lc(root.left, gMax), r = lc(root.right, gMax);
            if (root.left != null && root.left.val == root.val + 1) 
                ans = l + 1;
            if (root.right != null && root.right.val == root.val + 1) 
                ans = Math.max(ans, r + 1);
            
            gMax[0] = Math.max(gMax[0], ans);
            return ans;
        }
    }

Log in to reply
 

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