Easy Java recursive solution and iterative DFS and BFS solutions


  • 1
    A
    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;
            Queue<TreeNode> remain = new LinkedList<>();
            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);
            }
        }
    }
    

Log in to reply
 

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