Concise and Clear Post Order solution


  • 0
    N
    int max = 0;
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        helper(root);
        return max;
    }
    private int[] helper(TreeNode root) {
        if (root == null) {
            return null;
        }
        int[] curr = {1, 1, root.val};
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        if (left != null) {
            if (root.val == left[2] + 1) {
                curr[0] = Math.max(curr[0], left[0] + 1);
            } else if (root.val == left[2] - 1) {
                curr[1] = Math.max(curr[1], left[1] + 1);
            }
        }
        if (right != null) {
            if (root.val == right[2] + 1) {
                curr[0] = Math.max(curr[0], right[0] + 1);          
            } else if (root.val == right[2] - 1) {
                curr[1] = Math.max(curr[1], right[1] + 1);            
            }            
        }
        max = Math.max(max, curr[0] + curr[1] - 1);
        return curr;
    }

  • 0
    N

    Basically, we want to store three fields for each TreeNode. Namely, valueForIncrease, valueForDecrease and the TreeNode value itself.


Log in to reply
 

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