Easy O(n) Java Solution for 2 problems


  • 1
    L

    The main idea is to record each node's LCS, which is the value returned by helper function. At each helper function, we need to update max LCS.
    Binary Tree Longest Consecutive Sequence

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

    Same idea, but the helper function need to return the 2 LCS value, one is upward, the other is downward.
    Binary Tree Longest Consecutive Sequence II

    public class Solution {
        int res;
        public int longestConsecutive(TreeNode root) {
            res = 0;
            helper(root);
            return res;
        }
        public int[] helper(TreeNode root){
            int[] cur = new int[2];
            if(root == null) return cur;
            int[] left = helper(root.left);
            int[] right = helper(root.right);
            
            if(root.left != null){
                if(root.left.val != root.val - 1) left[0] = 0;
                if(root.left.val != root.val + 1) left[1] = 0;
            }
            if(root.right != null){
                if(root.right.val != root.val - 1) right[0] = 0;
                if(root.right.val != root.val + 1) right[1] = 0;
            }
            
            cur[0] = Math.max(left[0], right[0]) + 1;
            cur[1] = Math.max(left[1], right[1]) + 1;
            
            res = Math.max(res, cur[0] + cur[1] - 1);
            return cur;
        }
    }
    

  • 0
    J
    This post is deleted!

Log in to reply
 

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