Leetcode: 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.

递归法

复杂度

时间O(n) 空间O(h)

思路

因为要找最长的连续路径，我们在遍历树的时候需要两个信息，一是目前连起来的路径（curLen）有多长（以当前节点为终点），二是目前路径的上一个节点的值(preVal)。

每一次递归，先检查当前节点是否比上一节点大1, 是，curLen++, 否curLen置1 (curLen = (cur.val==preVal+1)? curLen+1 : 1)

返回时，返回如下三个中的大者：

1. curLen: 以当前节点为结束节点的最大路径

2. root.left递归返回值：以左子树以下某节点为终点的最大路径

3. root.right递归返回值：以右子树以下某节点为终点的最大路径

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int longestConsecutive(TreeNode root) {
12         if (root == null) return 0;
13         return helper(root, 0, Integer.MAX_VALUE);
14     }
15     
16     public int helper(TreeNode cur, int curLen, int preVal) {
17         curLen = (cur.val == preVal+1)? curLen+1 : 1;
18         int left=0, right=0;
19         if (cur.left != null) 
20             left = helper(cur.left, curLen, cur.val);
21         if (cur.right != null)
22             right = helper(cur.right, curLen, cur.val);
23         return Math.max(curLen, Math.max(left, right));
24     }
25 }

（默认）其实我自己的方法更好：在递归里不需要保存上一个节点值，在当前节点cur就把cur.left和cur.right的curLen算出来；也不需要return type，把结果res存成一个 Instance variable，在recursion里面找寻最大的curLen, 一旦找到就记录下来，记录在instance variable res里面。最后返回res。以下提供arraylist存res和直接res是一个instance variable的做法

 1 public class Solution {
 2     int res = 0;
 3     
 4     public int longestConsecutive(TreeNode root) {
 5         if (root == null) return 0;
 6         helper(root, 1);
 7         return res;
 8     }
 9     
10     public void helper(TreeNode root, int curLen) {
11         if (curLen > res) res = curLen;
12         if (root.left != null) {
13             int left = (root.left.val==root.val+1)? curLen+1 : 1;
14             helper(root.left, left);
15         }
16         if (root.right != null) {
17             int right = (root.right.val==root.val+1)? curLen+1 : 1;
18             helper(root.right, right);
19         }
20     }
21 }

上面这段code13行和17行得用一个variable去存，直接在14行和18行里面算在大case里面会有stackoverflow的错误

discuss 里 vote最高：

 1 public class Solution {
 2     private int max = 0;
 3     public int longestConsecutive(TreeNode root) {
 4         if(root == null) return 0;
 5         helper(root, 0, root.val);
 6         return max;
 7     }
 8     
 9     public void helper(TreeNode root, int cur, int target){
10         if(root == null) return;
11         if(root.val == target) cur++;
12         else cur = 1;
13         max = Math.max(cur, max);
14         helper(root.left, cur, root.val + 1);
15         helper(root.right, cur, root.val + 1);
16     }
17 }