Leetcode/G家 -- 298. Binary Tree Longest Consecutive Sequence(dfs)

298. Binary Tree Longest Consecutive Sequence(dfs)

• Difficulty: Medium

https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.
(Memorize 1st time I solve the medium dfs on my own)

思路：a. use a global var max to track maximum length, recursively travel tree,
            if(cur.val == last.val +1 )cur len++, else set cur len be 1
          b. recursion with out global variable by having left,right for len of subtrees,
           find the max among (len(root),left,right) for overall max

Complexity: O(n) like tree traversal

解法a

public class Solution {
    private int max = 0;//global var
    public int longestConsecutive(TreeNode root) {
        if(root==null)return 0;
        helper(root,0,root.val);//node,len,last value
        return max;
    }
    public void helper(TreeNode root,int len,int val){
        if(root==null)return;
        if(root.val == val+1)len++;
        else len = 1;
        max = Math.max(max,len);
        helper(root.left,len,root.val);
        helper(root.right,len,root.val);
    }
}

解法b

public class Solution {
    public int longestConsecutive(TreeNode root) {
        if(root==null)return 0;
        return helper(root,0,root.val);//node,len,last value
    }
    public int helper(TreeNode root,int len,int val){
        if(root == null)return 0;
        if(root.val == val +1)len++;
        else len = 1;
        int left = helper(root.left,len,root.val);
        int right = helper(root.right,len,root.val);
        return Math.max(Math.max(left,right),len);//max bt 3
        //len means length from root, need when single element or longest path start from root.
    }
}