549.|549. Binary Tree Longest Consecutive Sequence II 549.BinaryTreeLongestConsecutiveSequ

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 / \ 23 Output: 2 Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2: Input: 2 / \ 13 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].

因为本题目可以是 child-Parent-child ，所以用"Post-order 分治上传"而不是preorder
Solution：Post-order 分治上传思路：
Time Complexity: O(N) Space Complexity: O(N) 递归
【549.|549. Binary Tree Longest Consecutive Sequence II】Solution Code：

/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */ public class Solution { int max = 0; class Result { TreeNode node; int inc; int des; }public int longestConsecutive(TreeNode root) { traverse(root); return max; }private Result traverse(TreeNode node) { if (node == null) return null; Result left = traverse(node.left); Result right = traverse(node.right); Result curr = new Result(); curr.node = node; curr.inc = 1; curr.des = 1; if (left != null) { if (node.val - left.node.val == 1) { curr.inc = Math.max(curr.inc, left.inc + 1); } else if (node.val - left.node.val == -1) { curr.des = Math.max(curr.des, left.des + 1); } }if (right != null) { if (node.val - right.node.val == 1) { curr.inc = Math.max(curr.inc, right.inc + 1); } else if (node.val - right.node.val == -1) { curr.des = Math.max(curr.des, right.des + 1); } }max = Math.max(max, curr.inc + curr.des - 1); return curr; } }