Neat Java Solution Single pass O(n)


  • 26
    public class Solution {
        int maxval = 0;
        public int longestConsecutive(TreeNode root) {
            longestPath(root);
            return maxval;
        }
        public int[] longestPath(TreeNode root) {
            if (root == null)
                return new int[] {0,0};
            int inr = 1, dcr = 1;
            if (root.left != null) {
                int[] l = longestPath(root.left);
                if (root.val == root.left.val + 1)
                    dcr = l[1] + 1;
                else if (root.val == root.left.val - 1)
                    inr = l[0] + 1;
            }
            if (root.right != null) {
                int[] r = longestPath(root.right);
                if (root.val == root.right.val + 1)
                    dcr = Math.max(dcr, r[1] + 1);
                else if (root.val == root.right.val - 1)
                    inr = Math.max(inr, r[0] + 1);
            }
            maxval = Math.max(maxval, dcr + inr - 1);
            return new int[] {inr, dcr};
        }
    }

  • 0
    Z

    Thanks for sharing, that's a very elegant solution!


  • 0
    E

    Why don't you have to do dcr = Math.max(dcr, r[1] + 1); for the left subtrees?


  • 0

    @erciyas Because I am first traversing left subtree and changing the value of inr and dcr and then traversing right subtree and finding max dcr and inr.


  • 0

    Thanks for sharing.


  • 0
    L
    This post is deleted!

  • 1
    6

    Instead of using Array, I think we can use positive or negative number to represent the increasing or decreasing order.

    '''

    private int h(TreeNode root, int pre) {
        if (root == null) {
            return 0;
        }
        int left = h(root.left, root.val);
        int right = h(root.right, root.val);
        
        if (left * right < 0) {
            max = Math.max(max, 1 + Math.abs(left) + Math.abs(right));
        } else {
            max = Math.max(max, 1 + Math.max(Math.abs(left), Math.abs(right)));
        }
        
        if (root.val - pre == 1) {
            return 1 + Math.max(0, Math.max(left, right));
        }
        if (root.val - pre == -1) {
            return -1 + Math.min(0, Math.min(left, right));
        }
        return 0;
    }
    

    '''


  • 1
    F

    Rewrite your code in the more readable way...

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

Log in to reply
 

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