549. Binary Tree Longest Consecutive Sequence II

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both
considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-
Parent-child order, where not necessarily be parent-child order.

Example 1:

Input:
      1
     / \
    2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].



Example 2:

Input:
      2
     / \
    1   3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].



Note: All the values of tree nodes are in the range of [-1e7, 1e7].
  • break three sum to two sum

int result = 0;
 public int longestConsecutive(TreeNode root) {
     traverse(root);
     return result;
 }

 public int[] traverse(TreeNode root) {
     if(root == null) return new int[]{0,0,0};
     int[] left = traverse(root.left), right = traverse(root.right);
     int leftIn = root.val == left[0]+1 ? 1 + left[1] : 1;
     int rightIn = root.val == right[0]+1 ? 1 + right[1] : 1;
     int leftDe = root.val == left[0]-1 ? 1 + left[2] : 1;
     int rightDe = root.val == right[0]-1 ? 1 + right[2] : 1;
     int leftInRightDe = leftIn + rightDe - 1;
     int leftDeRightIn = leftDe + rightIn - 1;
     int max = Math.max(leftInRightDe, leftDeRightIn);
     result = Math.max(max, result);
     return new int[] {root.val, Math.max(leftIn, rightIn), Math.max(rightDe, leftDe)};
 }