Simple Recursive DFS without global variable


  • 49
    N
    public class Solution {
        public int longestConsecutive(TreeNode root) {
            return (root==null)?0:Math.max(dfs(root.left, 1, root.val), dfs(root.right, 1, root.val));
        }
        
        public int dfs(TreeNode root, int count, int val){
            if(root==null) return count;
            count = (root.val - val == 1)?count+1:1;
            int left = dfs(root.left, count, root.val);
            int right = dfs(root.right, count, root.val);
            return Math.max(Math.max(left, right), count);
        }
    }

  • 0
    G

    Nice work! Avoided using global variable.


  • 0
    C

    Can you please explain why not use global variables? Thanks!


  • 1
    J

    @chuR maybe that means if you want to examine another tree root, you should initialize a new object of class Solution. Because a global var max would influence this.


  • 0
    D

    @Jrui well, you can actually reset the global variable before return. I think this problem is perfect to use instance variable.

    int tmp = this.max;
    this.max = 0;
    return tmp;


  • 1
    P

    My another approach is to take max of the length till now and the max of left and right length. Following is the simple implementation :

    public int longestConsecutive(TreeNode root) {
            if(root == null)
                return 0;
            return longestConsecutive(root, null, 0);
        }
        public int longestConsecutive(TreeNode root, TreeNode prev, int len) {
            if(root == null)
                return len; // reached the leaf node.
    
            int leftLen = 0, rightLen = 0;
            if(prev != null && root.val == prev.val + 1) { // Increasing node found
                leftLen = longestConsecutive(root.left, root, len + 1);
                rightLen = longestConsecutive(root.right, root, len + 1);
            }
            else { // This node breaks the increasing property. So start again from here.
                leftLen = Math.max(len, longestConsecutive(root.left, root, 1));
                rightLen = Math.max(len, longestConsecutive(root.right, root, 1));
            }
    
                
            return Math.max(leftLen, rightLen);
            
        }
    

  • 0

    Same idea. My python code.

    class Solution(object):
        def longestConsecutive(self, root):
            
            def _dfs(node, parent, cur_l):
                if not node:
                    return cur_l
                if parent == None or node.val != parent + 1:
                    cur_l = 0
                cur_l += 1
                return max(_dfs(node.left, node.val, cur_l), _dfs(node.right, node.val, cur_l), cur_l)
                
            return _dfs(root, None, 0)
    

  • 1
    A

    Similar idea but there is no need to separate the recursion for left and right nodes in the main function

    public int longestConsecutive(TreeNode root) 
        {
            if(root == null)    return 0;
            int res = dfs(root, 1, root.val);
            return res;
        }
        private int dfs(TreeNode node, int count, int prev)
        {
            if(node == null)    return count;
            if(node.val == prev + 1)    count ++;
            else    count = 1;
            int left = dfs(node.left, count, node.val);
            int right = dfs(node.right, count, node.val);
            return Math.max(Math.max(left,right), count);
        }
    

  • 0
    T

    @Anylnb I really like your solution, its clean and simple. Keep it up.
    I came up with this solution. Here I am passing the currentCount and the maxCount at each step.

    
        public int longestConsecutive(TreeNode root){
            return helper(root, null, 0, 0);
        }
    
        private int helper(TreeNode root, TreeNode prev, int cnt, int mx){
            if (null == root){
                return Math.max(cnt, mx);
            }
    
            if (null != prev && root.val - 1 == prev.val) {
                cnt++;
            }else {
                mx = Math.max(cnt, mx);
                cnt = 1;
            }
    
            int left = helper(root.left, root, cnt, mx);
            int right = helper(root.right, root, cnt, mx);
    
            return Math.max(left, right);
        }
    
    

  • 0
    Y

    In the main function, you do not need to call dfs() to both left and right, just call return (root==null)? 0:dfs(root,1,root.val);
    since the last recursion will automatically return the bigger one between the left and right node of the root.


  • 0
    T
    Make it more simplified.
    
    public int longestConsecutive(TreeNode root) {
        if(root==null) return 0;
        return Helper(root, 1, root.val);
    }
    
    public int Helper(TreeNode root, int count, int val){
        if(root==null) return count;
        count = (root.val - val == 1)?count+1:1;
        int left = Helper(root.left, count, root.val);
        int right = Helper(root.right, count, root.val);
        return Math.max(Math.max(left, right), count);
    }

Log in to reply
 

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