LeetCode 298 - Binary Tree Longest Consecutive Sequence
http://bookshadow.com/weblog/2017/04/09/leetcode-binary-tree-longest-consecutive-sequence-ii/
用分治法。
我们用ResultType来记录从某一个点往下走的时候递增的最大路径和递减的最大路径，以及一个全局的最长路径。
在某一点，全局的最长路径就是：
1：左子树中遇到的最长路径
2：右子树中遇到的最长路径
3：通过当前点的最长路径
这三者的最大值。
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
思路
和Binary Tree Longest Consecutive Sequence II一样的做法。
II只要check一下left和right。
这题因为有多个子节点，所以要用一个循环来check所有。
http://bookshadow.com/weblog/2017/04/09/leetcode-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:
Example 2:
解法I 一趟遍历
时间复杂度O(n) n为节点的个数
采用bottom-up的方法dfs. 每个点同时维护能向下延展的最大increasing 和 decreasing长度.
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};
} 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;
}
解法II 递归 + 遍历二叉树
时间复杂度O(n^2) n为节点的个数
https://xuezhashuati.blogspot.com/2017/04/lintcode-619-binary-tree-longest.html用分治法。
我们用ResultType来记录从某一个点往下走的时候递增的最大路径和递减的最大路径，以及一个全局的最长路径。
在某一点，全局的最长路径就是：
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
思路
和Binary Tree Longest Consecutive Sequence II一样的做法。
II只要check一下left和right。
这题因为有多个子节点，所以要用一个循环来check所有。
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); }
