Java Recursive Solution


  • 0
    Y

    Very straight forward solution

    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int[] result = new int[1];
        result[0] = 1;
        helper(root.left, root.val, 1, result);
        helper(root.right, root.val, 1, result);
        
        return result[0];
    }
    
    public void helper(TreeNode node, int prev, int pathLen, int[] result) {
        if (node == null) {
            result[0] = Math.max(result[0], pathLen);
            return;
        }
        
        if (prev == node.val - 1) {
            helper(node.left, node.val, pathLen + 1, result);
            helper(node.right, node.val, pathLen + 1, result);
        } else {
            result[0] = Math.max(result[0], pathLen);
            helper(node.left, node.val, 1, result);
            helper(node.right, node.val, 1, result);
        }
    }

  • 0
    H

    Why don't you just use a global variable?

    public int longestConsecutive(TreeNode root) {
        result = 0;
        DFS(root, null, 0);
    
        
        return result;
    }
    
    int result;
    
    public void DFS(TreeNode root, TreeNode prev, int len){
        if(root == null) return;
        
        if(prev != null && root.val != prev.val +1){
            len = 0;
        }
        
        len ++;//include curr Node
        result = Math.max(result, len);
        if(root.left != null) DFS(root.left, root, len);
        if(root.right != null) DFS(root.right, root, len);
    }

Log in to reply
 

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