Amazon Interview Question SDE1s
Country: United States
Interview Type: In-Person
I will level reverse the tree and create a new tree which has the same structure as the original tree but the node's value is the length of consecutive number sequence calculated from its root. The initial value of new tree's node is 1. If the child is continues to its root then child's node value ++. In your case, newTree(2)=1, newTree(3)=2, newTree(4)=3, newTree(6)=1.
I'm not sure whether have to consider case like (3,2,1). If that is the case, we can design the new tree node that has two values, upLen and downLen.
Not sure whether I understand the problem correctly. Following is my idea:
Let Mx be the maximum length of consecutive number sequence (CNS) that ends at node x.
Then for each child c of x, the Mc - maximum length of CNS that ends at c, is calculated as following:
If the value of c (e.g. 4) is consecutive number after value of x (e.g. 3), then Mc = Mx +1
otherwise, start new sequence at c: Mc = 1.
Time complexity: O(N), N = number of nodes in the tree.
Pseudo C++ code (Recursion):
struct TreeNode{
int val;
int maxLen; // Mx -- max length of consecutive number sequence that ends at this node.
TreeNode* V[]; // all childs
}
void findMaxLength(TreeNode x, TreeNode parent){
if (x.val == parent.val +1 ) x.maxLen = parent.maxLen + 1;
else x.maxLen = 1;
if (x.maxLen > globalMax) globalMax = x.maxLen;
for each child c of x do
findMaxLength(c, x);
};
main(){
root.maxLen = 1;
globalMax = 0;
for each child v of root
findMaxLength(v,root);
cout <<globalMax<<endl;
}
I don't really thing you need to do a level order traversal for this. Though at the first glance at the problem, you might be tempted to use. We can create a array of size equal to the depth of the tree to store all the path from root to leaf. Whenever we hit the leaf node, the array will contain the path from root to leaf. Then you have to do a simple comparsion operation to get maximum sequence count.
private int depth(Node root) {
if(root == null) return 0;
else return 1 + Math.max(depth(root.leftChild), depth(root.rightChild));
}
public int maxSequence() {
int depth = depth();
int[] path = new int[depth];
return maxSequence(root, path, 0);
}
private int maxSequence(Node node, int[] path, int level) {
if(node == null) {
return getSequenceLength(path, level);
}
path[level] = node.element;
return Math.max(maxSequence(node.leftChild, path, level+1),
maxSequence(node.rightChild, path, level+1));
}
private int getSequenceLength(int[] path, int level) {
int count = 1;
int depth = 0;
while(depth < level) {
for(int index = 0; index < level-1; index++) {
if(path[index] < path[index+1]) {
count++;
} else {
depth = index + 1;
}
}
return count;
}
return count;
}
I'm not sure if the code can be optimized any further.
Something like this? (I feel like I must be missing something):
void MaxConsecLength(node* pNode, int& maxLen, int curLen, int prevVal)
{
curLen = pNode->value == prevVal + 1 ? curLen + 1 : 1;
maxLen = std::max(curLen, maxLen);
for (node* pChild: pNode->children)
MaxConsecLength(pChild, maxLen, curLen, pNode->value);
}
...
int maxLen = 0;
MaxConsecLength(pRoot, maxLen, 0, pRoot->value);
This can be done using recursion. The idea is to keep track of ROOT to LEAF path.
Let me explain it to you with an example.
Let the given tree is like below.
1
/ | \
2 4 66
/ | \
3 6 3
/
10
/
11
/
12
/
13
now we recursively traverse the tree and store ROOT to LEAF path in an array.
In above example ROOT to LEAF paths are:
1,2,3,10,11,12,13
1,2,6
1,2,3
1,4
1,6
While traversing the tree, keep track of maximum continuous sequence.
Like in 1st recursive call, we have path array and length array(it stores the maximum length till the index).
1,2,3,10,11,12,13
1,2,3, 1, 2 , 3, 4
Now count the maximum length i.e. 4 and store in our answer MAX.
Similarly for other recursive calls do the same and update MAX if required.
At last MAX would be our required answer.
Time complexity:
If H is maximum height of tree and L are total number of leaf nodes.
Then worst case wold be of O(L*H)
static int maxseqlen(tree_t *root, int count, int prev_data, int max)
{
if(root==NULL)
return max;
if(count>max)
max=count;
if(root->num==prev_data+1)
{
max=maxseqlen(root->left,count+1,root->num,max);
}
else
max=maxseqlen(root->left,1,root->num,max);
if(root->num==prev_data+1)
{
max=maxseqlen(root->right,count+1,root->num,max);
}
else
max=maxseqlen(root->right,1,root->num,max);
return max;
}
max=maxseqlen(root,0,0,0);
printf("Max seq is :%d",max+1);
static int maxseqlen(tree_t *root, int count, int prev_data, int max)
{
if(root==NULL)
return max;
if(count>max)
max=count;
if(root->num==prev_data+1)
{
max=maxseqlen(root->left,count+1,root->num,max);
}
else
max=maxseqlen(root->left,1,root->num,max);
if(root->num==prev_data+1)
{
max=maxseqlen(root->right,count+1,root->num,max);
}
else
max=maxseqlen(root->right,1,root->num,max);
return max;
}
public class MaxConsecutiveIntInTree {
public static class Node {
private int val;
private LinkedList<Node>children;
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public LinkedList<Node> getChildren() {
return children;
}
public void setChildren(LinkedList<Node> children) {
this.children = children;
}
}
public static int getConsecutiveCount(Node n, Node p, int count) {
if(n == null) return 0;
int res, max;
res = 0; max = count;
if(n.getChildren() != null) {
for(Node c : n.getChildren()) {
int base = 1;
if(n.getVal() + 1 == c.getVal())
if(p != null && p.getVal() + 1 == n.getVal())
base = count+1;
else
base = 2;
res = getConsecutiveCount(c, n, base);
if(res > max)
max = res;
}
}
return max;
}
public static void main(String[] args) {
/**
* 3
* / | \
* 2 5 8
* / \
* 1 6
* \
* 7
* \
* 9
*/
Node n1 = new Node();
n1.setVal(1);
Node n2 = new Node();
n2.setVal(2);
Node n3 = new Node();
n3.setVal(3);
Node n4 = new Node();
n4.setVal(4);
Node n5 = new Node();
n5.setVal(5);
Node n6 = new Node();
n6.setVal(6);
Node n7 = new Node();
n7.setVal(7);
Node n8 = new Node();
n8.setVal(8);
Node n9 = new Node();
n9.setVal(9);
LinkedList<Node> c1 = new LinkedList<Node>();
c1.add(n2);
c1.add(n5);
c1.add(n8);
n3.setChildren(c1);
LinkedList<Node> c2 = new LinkedList<Node>();
c2.add(n1);
c2.add(n6);
n5.setChildren(c2);
LinkedList<Node> c3 = new LinkedList<Node>();
c3.add(n7);
n6.setChildren(c3);
LinkedList<Node> c4 = new LinkedList<Node>();
c4.add(n9);
n7.setChildren(c4);
System.out.println(getConsecutiveCount(n3, null, 0));
}
}
I just have the pseudocode for this one and I think it should work correctly. It takes O(n) in the worst case.
HashMap<String, int> hm = new HashMap<String, int>(); // This is the only Java code
function getHeights(node, height) :
flag <- false
if node==nil :
return
end if
for child in node->children :
if child->val - 1 == node->val :
flag <- true
getHeights(child, height+1)
end if
end for
if flag == false : // That is, there is no child node which belongs to the sequence
hm.add(node, height)
end if
end function
function getMaxHeight()
(node, val) <- max(hm)
// from node, we can keep travelling to its parent node to get
// the actual trace of the sequence
end function
The idea is to do this recursively by looking at all your children and seeing if you extend any of them. Just choose the longest of the child sequences to extend.
Whenever you are done with a node, see if its extension is longer than the longest. If it is, then update the longest.
#include <stdio.h>
#include <stdlib.h>
#include <sys/param.h>
int longest = 0;
struct Node {
int value;
struct Node **children;
int cChildren;
};
typedef struct Node Node;
int findLongest(Node *node) {
int myLongest = 1;
for (int iChild = 0; iChild < node->cChildren; iChild++) {
Node *child = node->children[iChild];
int childLongest = findLongest(child);
if (child->value == (node->value + 1)) {
if ((childLongest + 1) > myLongest) {
myLongest = childLongest + 1;
}
}
}
if (myLongest > longest) {
longest = myLongest;
}
return myLongest;
}
Working Java solution:
import java.lang.Math;
public class MaxSeqLenInTree {
private static class TreeNode {
private int value;
private TreeNode left, right;
public TreeNode(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public TreeNode leftChild() {
return left;
}
public TreeNode rightChild() {
return right;
}
public void setLeftChild(TreeNode node) {
left = node;
}
public void setRightChild(TreeNode node) {
right = node;
}
}
public static int maxSeqLen(TreeNode node) {
if (node == null)
return 0;
else
return maxSeqLen(node, node.getValue(), 1, 1);
}
private static int maxSeqLen(TreeNode node, int parentValue, int currentSeqLen, int maxSeqLen) {
if (node == null) return 0;
if (node.getValue() == parentValue + 1)
currentSeqLen++;
else
currentSeqLen = 1;
maxSeqLen = Math.max(currentSeqLen, maxSeqLen);
int leftMax = maxSeqLen(node.leftChild(), node.getValue(), currentSeqLen, maxSeqLen);
int rightMax = maxSeqLen(node.rightChild(), node.getValue(), currentSeqLen, maxSeqLen);
return Math.max(maxSeqLen, Math.max(leftMax, rightMax));
}
public static void main(String[] args) {
TreeNode n0 = new TreeNode(0);
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
n3.setLeftChild(n5);
n3.setRightChild(n2);
n5.setLeftChild(n0);
n5.setRightChild(n6);
n2.setLeftChild(n4);
n2.setRightChild(n1);
n0.setLeftChild(n9);
n6.setLeftChild(n7);
n4.setRightChild(n8);
System.out.println(maxSeqLen(n3));
}
}
Working Java solution.
import java.lang.Math;
public class MaxSeqLenInTree {
private static class TreeNode {
private int value;
private TreeNode left, right;
public TreeNode(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public TreeNode leftChild() {
return left;
}
public TreeNode rightChild() {
return right;
}
public void setLeftChild(TreeNode node) {
left = node;
}
public void setRightChild(TreeNode node) {
right = node;
}
}
public static int maxSeqLen(TreeNode node) {
if (node == null)
return 0;
else
return maxSeqLen(node, node.getValue(), 1, 1);
}
private static int maxSeqLen(TreeNode node, int parentValue, int currentSeqLen, int maxSeqLen) {
if (node == null) return 0;
if (node.getValue() == parentValue + 1)
currentSeqLen++;
else
currentSeqLen = 1;
maxSeqLen = Math.max(currentSeqLen, maxSeqLen);
int leftMax = maxSeqLen(node.leftChild(), node.getValue(), currentSeqLen, maxSeqLen);
int rightMax = maxSeqLen(node.rightChild(), node.getValue(), currentSeqLen, maxSeqLen);
return Math.max(maxSeqLen, Math.max(leftMax, rightMax));
}
public static void main(String[] args) {
TreeNode n0 = new TreeNode(0);
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
n3.setLeftChild(n5);
n3.setRightChild(n2);
n5.setLeftChild(n0);
n5.setRightChild(n6);
n2.setLeftChild(n4);
n2.setRightChild(n1);
n0.setLeftChild(n9);
n6.setLeftChild(n7);
n4.setRightChild(n8);
System.out.println(maxSeqLen(n3));
}
}
Working Java solution.
import java.lang.Math;
public class MaxSeqLenInTree {
private static class TreeNode {
private int value;
private TreeNode left, right;
public TreeNode(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public TreeNode leftChild() {
return left;
}
public TreeNode rightChild() {
return right;
}
public void setLeftChild(TreeNode node) {
left = node;
}
public void setRightChild(TreeNode node) {
right = node;
}
}
public static int maxSeqLen(TreeNode node) {
if (node == null)
return 0;
else
return maxSeqLen(node, node.getValue(), 1, 1);
}
private static int maxSeqLen(TreeNode node, int parentValue, int currentSeqLen, int maxSeqLen) {
if (node == null) return 0;
if (node.getValue() == parentValue + 1)
currentSeqLen++;
else
currentSeqLen = 1;
maxSeqLen = Math.max(currentSeqLen, maxSeqLen);
int leftMax = maxSeqLen(node.leftChild(), node.getValue(), currentSeqLen, maxSeqLen);
int rightMax = maxSeqLen(node.rightChild(), node.getValue(), currentSeqLen, maxSeqLen);
return Math.max(maxSeqLen, Math.max(leftMax, rightMax));
}
public static void main(String[] args) {
TreeNode n0 = new TreeNode(0);
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
n3.setLeftChild(n5);
n3.setRightChild(n2);
n5.setLeftChild(n0);
n5.setRightChild(n6);
n2.setLeftChild(n4);
n2.setRightChild(n1);
n0.setLeftChild(n9);
n6.setLeftChild(n7);
n4.setRightChild(n8);
System.out.println(maxSeqLen(n3));
}
}
Working Java solution.
import java.lang.Math;
public class MaxSeqLenInTree {
private static class TreeNode {
private int value;
private TreeNode left, right;
public TreeNode(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public TreeNode leftChild() {
return left;
}
public TreeNode rightChild() {
return right;
}
public void setLeftChild(TreeNode node) {
left = node;
}
public void setRightChild(TreeNode node) {
right = node;
}
}
public static int maxSeqLen(TreeNode node) {
if (node == null)
return 0;
else
return maxSeqLen(node, node.getValue(), 1, 1);
}
private static int maxSeqLen(TreeNode node, int parentValue, int currentSeqLen, int maxSeqLen) {
if (node == null) return 0;
if (node.getValue() == parentValue + 1)
currentSeqLen++;
else
currentSeqLen = 1;
maxSeqLen = Math.max(currentSeqLen, maxSeqLen);
int leftMax = maxSeqLen(node.leftChild(), node.getValue(), currentSeqLen, maxSeqLen);
int rightMax = maxSeqLen(node.rightChild(), node.getValue(), currentSeqLen, maxSeqLen);
return Math.max(maxSeqLen, Math.max(leftMax, rightMax));
}
public static void main(String[] args) {
TreeNode n0 = new TreeNode(0);
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
n3.setLeftChild(n5);
n3.setRightChild(n2);
n5.setLeftChild(n0);
n5.setRightChild(n6);
n2.setLeftChild(n4);
n2.setRightChild(n1);
n0.setLeftChild(n9);
n6.setLeftChild(n7);
n4.setRightChild(n8);
System.out.println(maxSeqLen(n3));
}
}
Working Java solution.
import java.lang.Math;
public class MaxSeqLenInTree {
private static class TreeNode {
private int value;
private TreeNode left, right;
public TreeNode(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public TreeNode leftChild() {
return left;
}
public TreeNode rightChild() {
return right;
}
public void setLeftChild(TreeNode node) {
left = node;
}
public void setRightChild(TreeNode node) {
right = node;
}
}
public static int maxSeqLen(TreeNode node) {
if (node == null)
return 0;
else
return maxSeqLen(node, node.getValue(), 1, 1);
}
private static int maxSeqLen(TreeNode node, int parentValue, int currentSeqLen, int maxSeqLen) {
if (node == null) return 0;
if (node.getValue() == parentValue + 1)
currentSeqLen++;
else
currentSeqLen = 1;
maxSeqLen = Math.max(currentSeqLen, maxSeqLen);
int leftMax = maxSeqLen(node.leftChild(), node.getValue(), currentSeqLen, maxSeqLen);
int rightMax = maxSeqLen(node.rightChild(), node.getValue(), currentSeqLen, maxSeqLen);
return Math.max(maxSeqLen, Math.max(leftMax, rightMax));
}
public static void main(String[] args) {
TreeNode n0 = new TreeNode(0);
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
n3.setLeftChild(n5);
n3.setRightChild(n2);
n5.setLeftChild(n0);
n5.setRightChild(n6);
n2.setLeftChild(n4);
n2.setRightChild(n1);
n0.setLeftChild(n9);
n6.setLeftChild(n7);
n4.setRightChild(n8);
System.out.println(maxSeqLen(n3));
}
}
I has written my own code, then take a look here and I am bit confused why you use competitor value in the recursion. As for me this is not necessary, because tree is recursion data structure so we can consider each node as sub-tree and resolve the task separably for each node. Here is my code with two tests:
import java.util.ArrayList;
import java.util.List;
/**
* Created by sis on 3/11/15.
*/
public class CareerCup_6285363834257408 {
static class Node {
int a;
List<Node> children = new ArrayList<>();
Node(int a) {
this.a = a;
}
void addChildren(int... nums) {
for (int n: nums) {
children.add(new Node(n));
}
}
Node getChild(int n) {
for (int i = 0; i < children.size(); i++) {
Node child = children.get(i);
if (child.a == n) {
return child;
}
}
throw new RuntimeException();
}
public static void main(String[] args) {
// Node root = test1();
Node root = test2();
int result = findMaxLength(root);
System.out.print(result);
}
private static Node test2() {
Node root = new Node(3);
root.addChildren(2, 5, 8);
Node five = root.getChild(5);
five.addChildren(1, 6);
Node six = five.getChild(6);
six.addChildren(7);
Node seven = six.getChild(7);
seven.addChildren(9);
return root;
}
private static Node test1() {
Node root = new Node(1);
root.addChildren(2, 3);
Node three = root.getChild(3);
three.addChildren(4, 6, 3);
Node four = three.getChild(4);
four.addChildren(5);
Node three1 = three.getChild(3);
three1.addChildren(8, 4, 9);
Node four1 = three1.getChild(4);
four1.addChildren(5);
Node five = four1.getChild(5);
five.addChildren(6);
return root;
}
private static int findMaxLength(Node root) {
if (root == null) {
return 0;
}
int result = 1;
for (Node child: root.children) {
if (child.a == root.a + 1) {
result = Math.max(result, findMaxLength(child) + 1);
} else {
result = Math.max(result, findMaxLength(child));
}
}
return result;
}
}
}
I has written my own code firstly and then took a look here. I am bit confused why all provided solution use competitor length value. As for me it is not necessary, because we can consider each node as sub-tree and resolve task for each node as it is a root, thus we will have two cases we continue with child the sequence or we start numeration from 1.
Here is my code:
import java.util.ArrayList;
import java.util.List;
/**
* Created by sis on 3/11/15.
*/
public class CareerCup_6285363834257408 {
static class Node {
int a;
List<Node> children = new ArrayList<>();
Node(int a) {
this.a = a;
}
void addChildren(int... nums) {
for (int n: nums) {
children.add(new Node(n));
}
}
Node getChild(int n) {
for (int i = 0; i < children.size(); i++) {
Node child = children.get(i);
if (child.a == n) {
return child;
}
}
throw new RuntimeException();
}
public static void main(String[] args) {
// Node root = test1();
Node root = test2();
int result = findMaxLength(root);
System.out.print(result);
}
private static Node test2() {
Node root = new Node(3);
root.addChildren(2, 5, 8);
Node five = root.getChild(5);
five.addChildren(1, 6);
Node six = five.getChild(6);
six.addChildren(7);
Node seven = six.getChild(7);
seven.addChildren(9);
return root;
}
private static Node test1() {
Node root = new Node(1);
root.addChildren(2, 3);
Node three = root.getChild(3);
three.addChildren(4, 6, 3);
Node four = three.getChild(4);
four.addChildren(5);
Node three1 = three.getChild(3);
three1.addChildren(8, 4, 9);
Node four1 = three1.getChild(4);
four1.addChildren(5);
Node five = four1.getChild(5);
five.addChildren(6);
return root;
}
private static int findMaxLength(Node root) {
if (root == null) {
return 0;
}
int result = 1;
for (Node child: root.children) {
if (child.a == root.a + 1) {
result = Math.max(result, findMaxLength(child) + 1);
} else {
result = Math.max(result, findMaxLength(child));
}
}
return result;
}
}
}
This can be done using recursion.
int maxLength = 0;
findMaxLength(node, parentNodeVal, lengthSoFar) {
if (node.Val == parentNodeVal + 1) {
if (lengthSoFar + 1 > maxLength) {
maxLength = lengthSoFar + 1;
}
lengthSoFar++
} else {
lengthSoFar = 1;
}
for (Node child: node.Children) {
findMaxLength(child, this.val, lengthSoFar);
}
}
Idea: Track longest contiguous subsequence ending at each node
To start off, LCS(root) = 1 and others build from this.
getLongest(Node n) {
getLongest(n, n.val, 1); // Start with root
}
getLongest(Node n, int prevVal, int prevCount) {
if (n == null) {return prevCount;} // Hit a leaf, count doesn't change
// Count essentially "resets" if the contiguous subsequence is broken
n.count = (n.val < prevVal) ? prevCount + 1 : 1;
// Find max count of all children
int maxCount;
for (Node c : n.children) {
int result = getLongest(c, n.val, n.count);
if (result > maxCount) {
maxCount = result;
}
}
// Return max increasing subseq ending at leafs reached from this node
return maxCount;
}
public static int length(Node node, Map<Node,Integer> nodeMap) {
int length = 0;
int tempLeft = 1;
int tempRight = 1;
if(node==null) { return 0;}
if(node.getLeftChild()!=null && node.getLeftChild().getValue() == node.getValue() + 1) {
tempLeft = tempLeft + length(node.getLeftChild(), nodeMap);
} else {
tempLeft =1;
length(node.getLeftChild(), nodeMap);
}
if(node.getRightChild() !=null && node.getRightChild().getValue() == node.getValue() + 1) {
tempRight = tempLeft + length(node.getRightChild(),nodeMap);
} else {
tempRight = 1;
length(node.getRightChild(), nodeMap);
}
length = tempLeft > tempRight ? tempLeft : tempRight;
nodeMap.put(node, length);
return length;
}
working java code :
public static int getMaxSeq(TreeNode root, int seq)
{
int maxSeq = 0;
int tempSeq = 0;
if(root.neighbours.size() == 0)
return seq;
for(TreeNode n : root.neighbours)
{
if(n.value == root.value + 1)
tempSeq = getMaxSeq(n,seq+1);
else
tempSeq = getMaxSeq(n,seq);
if(tempSeq > maxSeq)
maxSeq = tempSeq;
}
return maxSeq;
}
public static int getMaxSeq(TreeNode root, int seq)
{
int maxSeq = 0;
int tempSeq = 0;
if(root.neighbours.size() == 0)
return seq;
for(TreeNode n : root.neighbours)
{
if(n.value == root.value + 1)
tempSeq = getMaxSeq(n,seq+1);
else
tempSeq = getMaxSeq(n,seq);
if(tempSeq > maxSeq)
maxSeq = tempSeq;
}
return maxSeq;
}
public static int getMaxSeq(TreeNode root, int seq)
{
int maxSeq = 0;
int tempSeq = 0;
if(root.neighbours.size() == 0)
return seq;
for(TreeNode n : root.neighbours)
{
if(n.value == root.value + 1)
tempSeq = getMaxSeq(n,seq+1);
else
tempSeq = getMaxSeq(n,seq);
if(tempSeq > maxSeq)
maxSeq = tempSeq;
}
return maxSeq;
}
def maxConsecutivePathLength(root, path, prev_max, path_len):
if root:
if root.key > prev_max:
left_length, left_path = maxConsecutivePathLength(root.left, path + [root.key], root.key, path_len + 1)
right_length, right_path = maxConsecutivePathLength(root.right, path + [root.key], root.key, path_len + 1)
return (left_length, left_path) if max(left_length, right_length) == left_length \
else (right_length, right_path)
else:
left_length, left_path = maxConsecutivePathLength(root.left, [], root.key, 1)
right_length, right_path = maxConsecutivePathLength(root.right, [], root.key, 1)
p = [path, left_path, right_path]
l = [path_len, left_length, right_length]
return max(l), p[l.index(max(l))]
return path_len, path
This is variation of visiting a tree horizontally (i.e. visit root then its children at level 1, then at level 2 ...)
Trick is to maintain two queues, keeping one queue 'current', visiting its elements and adding its children in second queue. At the end of the loop, we swap the queues to make the other queue 'current' and clear the previous.
While visiting elements from 'current', we only add those children in the second queue, which are greater than the visiting element
active queue = q1
This looks like a variation of Longest subsequence. Instead of doing it on a single array, we are doing it on each path of the tree from root to leaf.
While traversing through the tree(DFS should work) we need to keep track of the continuous sequence ending at that node.
Also need to keep track of the max subsequence and its length until that point in the traversal.
- tomahawk March 12, 2015public int getLongest(Node root, List<Node> longestSoFar, List<Node> currentSequence){ if(root == null) return 0; for(Node child : root.childen){ //Check if the child not 1 greater than the root. Start new sequence if(child.value != 1 + root.value){ currentSequence = new ArrayList(); } currentSequence.add(child); //Check if the length of sequence ending at this node is greater than the largest sequence found so far. If yes, we have a new longest. if(currentSequence.size() > longestSoFar.size()){ longestSoFar = currentSequence; } getLongest(ch, longestSoFar, currentSequence); } //remove current node from sequence before returning up the stack currentSequence.remove(currentSequence.get(currentSequence.size()-1)); return longestSoFar.size();