[LintCode] 595 Binary Tree Longest Consecutive Sequence 解题报告

Description
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).


Example
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, not 3-2-1, so return 2.


思路
用分治法遍历整个树。同时维护一个最长序列的变量longest。
遍历每个节点的时候，测试一下加上这个节点的最长序列是多少，决定是否要更新longest。
遍历完整棵树，longest就是我们求的值。


Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @return the length of the longest consecutive sequence path
     */
    
    private int longest; 
     
    public int longestConsecutive(TreeNode root) {
        // Write your code here
        if (root == null) {
            return 0;
        }
        
        longest = 0;
        int rootResult = helper(root);
        return longest;
    }
    
    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = helper(root.left);
        int right = helper(root.right);
        
        int currLeft = 1;
        int currRight = 1;
        if (root.left != null) {
            currLeft = root.val + 1 == root.left.val ? left + 1 : 1;
        }
        if (root.right != null) {
            currRight = root.val + 1 == root.right.val ? right + 1 : 1;
        }
        
        int currResult = Math.max(currLeft, currRight);
        if (currResult > longest) {
            longest = currResult;
        }
        
        return currResult;
    }
}