Neat Java Solution Single pass O(n)


  • 29
    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;
    }
    

    '''


  • 3
    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};
        }
    }
    

  • 0
    I

    @erciyas vinod23 gave your the answer, its value changed previously so we have to find the max. If you did right subtree operation first, you should do same thing at left tree


Log in to reply
 

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