## Monday, April 17, 2017

### LeetCode 549 - Binary Tree Longest Consecutive Sequence II

LeetCode 298 - Binary Tree Longest Consecutive Sequence
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].```

```定义函数solve(root)，递归求解以root为根节点向子节点方向（parent-child）的路径中，最大连续递增路径长度inc，以及最大连续递减路径长度dec

https://discuss.leetcode.com/topic/85764/neat-java-solution-single-pass-o-n
``````    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};
}``````
https://discuss.leetcode.com/topic/85745/java-solution-binary-tree-post-order-traversal
``````    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;
}``````

```定义函数maxLength，递归计算从根节点出发向叶子节点可以得到的最长连续路径长度。

https://xuezhashuati.blogspot.com/2017/04/lintcode-619-binary-tree-longest.html

1：左子树中遇到的最长路径
2：右子树中遇到的最长路径
3：通过当前点的最长路径

```    class ResultType {
int maxLength;
int maxUp;
int maxDown;
public ResultType(int maxLength, int maxUp, int maxDown) {
this.maxLength = maxLength;
this.maxUp = maxUp;
this.maxDown = maxDown;
}
}
public int longestConsecutive2(TreeNode root) {
ResultType result = helper(root);
return result.maxLength;
}

public ResultType helper(TreeNode root) {

if (root == null) {
return new ResultType(0, 0, 0);
}

ResultType left = helper(root.left);
ResultType right = helper(root.right);

int up = 0;
int down = 0;

if (root.left != null && root.left.val + 1 == root.val) {
down = Math.max(down, left.maxDown + 1);
}

if (root.left != null && root.left.val - 1 == root.val) {
up = Math.max(up, left.maxUp + 1);
}

if (root.right != null && root.right.val + 1 == root.val) {
down = Math.max(down, right.maxDown + 1);
}

if (root.right != null && root.right.val - 1 == root.val) {
up = Math.max(up, right.maxUp + 1);
}

int max = Math.max(Math.max(left.maxLength, right.maxLength), up + down + 1);
return new ResultType(max, up, down);
}```

LintCode - 619 Binary Tree Longest Consecutive Sequence III
https://xuezhashuati.blogspot.com/2017/04/lintcode-619-binary-tree-longest_22.html
It's follow up problem for Binary Tree Longest Consecutive Sequence II

Given a k-ary tree, find the length of the longest consecutive sequence path.
The path could be start and end at any node in the tree

Example
An example of test data: k-ary tree 5<6<7<>,5<>,8<>>,4<3<>,5<>,3<>>>, denote the following structure:
5
/   \
6     4
/|\   /|\
7 5 8 3 5 3
Return 5, // 3-4-5-6-7

II只要check一下left和right。

```    class ResultType {
int globalMax;
int maxUp;
int maxDown;
public ResultType(int globalMax, int maxUp, int maxDown) {
this.globalMax = globalMax;
this.maxUp = maxUp;
this.maxDown = maxDown;
}
}

public int longestConsecutive3(MultiTreeNode root) {
return helper(root).globalMax;
}

public ResultType helper(MultiTreeNode root) {

if (root == null) {
return new ResultType(0, 0, 0);
}

int maxUp = 0;
int maxDown = 0;
int max = Integer.MIN_VALUE;

for (MultiTreeNode child : root.children) {

if (child == null) {
continue;
}

ResultType childResult = helper(child);
if (child.val + 1 == root.val) {
maxDown = Math.max(maxDown, childResult.maxDown + 1);
}

if (child.val - 1 == root.val) {
maxUp = Math.max(maxUp, childResult.maxUp + 1);
}

max = Math.max(Math.max(max, childResult.globalMax), maxUp + maxDown + 1);
}

return new ResultType(max, maxUp, maxDown);
}```