LeetCode : 298. Binary Tree Longest Consecutive Sequence

[congr]

https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/

[congr]

O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int longest = 0;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        postOrder(root);
        return longest;
    }

    int postOrder(TreeNode root) {
        if (root == null) return 0;

        int left = postOrder(root.left);
        int right = postOrder(root.right);

        int len = 1; // this node itself 
        int leftVal = root.left == null ? 0 : root.left.val;
        int rightVal = root.right == null ? 0 : root.right.val;

        if (leftVal - root.val == 1 && rightVal - root.val == 1)
            len = Math.max(left, right) + 1;
        else if (leftVal - root.val == 1)
            len = left + 1;
        else if (rightVal - root.val == 1)
            len = right + 1;

        longest = Math.max(longest, len);

        return len;
    }
}