Easy Java recursive solution and iterative DFS and BFS solutions

1. Recursive solution
``````public class Solution {
private int max; // A global parameter for recording the max length of sequence all the way
public int longestConsecutive(TreeNode root) {
if (root == null) return 0;
helper(root, 0, root.val);
return max;
}
private void helper(TreeNode root, int cur, int target) {
if (root == null) return;
if (root.val == target) cur ++; // If the condition of consecution is satisfied, increment the temporary length.
else cur = 1;// If not, record a new temporary length;
max = Math.max(cur, max);
helper(root.left, cur, root.val + 1);
helper(root.right, cur, root.val + 1);
}
}
``````
1. Iterative solutions
DFS the whole tree in preorder way with a stack and BFS the whole tree with a queue. Utilize a HashMap to keep record the length of the consecutive sequence so far for each node.
2.1 DFS
``````public class Solution {
public int longestConsecutive(TreeNode root) {
int max = 0;
if (root == null) return max;
Map<TreeNode, Integer> consecutive = new HashMap<TreeNode, Integer>();
Stack<TreeNode> remain = new Stack<>();
TreeNode node = root;
remain.push(node);
consecutive.put(node, 1);
while(!remain.isEmpty()) {
node = remain.pop();
doCount(consecutive, remain, node, node.right);
doCount(consecutive, remain, node, node.left);
max = Math.max(max, consecutive.get(node));
}
return max;
}
private void doCount(Map<TreeNode,Integer> consecutive, Stack<TreeNode> remain, TreeNode root, TreeNode child) {
if (child != null) {
if (child.val == root.val + 1) {
consecutive.put(child, consecutive.get(root) + 1);
} else {
consecutive.put(child, 1);
}
remain.push(child);
}
}
}
``````

2.2 BFS

``````public class Solution {
public int longestConsecutive(TreeNode root) {
int max = 0;
if (root == null) return max;
Map<TreeNode, Integer> consecutive = new HashMap<>();
TreeNode node = root;
remain.offer(node);
consecutive.put(node, 1);
while(!remain.isEmpty()) {
node = remain.poll();
doCount(consecutive, remain, node, node.left);
doCount(consecutive, remain, node, node.right);
max = Math.max(max, consecutive.get(node));
}
return max;
}
private void doCount(Map<TreeNode, Integer> consecutive, Queue<TreeNode> remain, TreeNode root, TreeNode child) {
if (child != null) {
if (child.val == root.val + 1) {
consecutive.put(child, consecutive.get(root) + 1);
} else {
consecutive.put(child, 1);
}
remain.offer(child);
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.