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

Description
Given a binary tree, find the length of the longest consecutive sequence path.
The path could be start and end at any node in the tree



Example
    1
   / \
  2   0
 /
3
Return 4 // 0-1-2-3-4



思路
用分治法。
我们用ResultType来记录从某一个点往下走的时候递增的最大路径和递减的最大路径，以及一个全局的最长路径。
在某一点，全局的最长路径就是：
1：左子树中遇到的最长路径
2：右子树中遇到的最长路径
3：通过当前点的最长路径
这三者的最大值。



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
     */
    
    class ResultType {
        int maxLength;
        int maxUp;
        int maxDown;
        public ResultType(int maxLength, int maxUp, int maxDown) {
            this.maxLength = maxLength;
            this.maxUp = maxUp;
            this.maxDown = maxDown;
        }
    }
    public int longestConsecutive2(TreeNode root) {
        // Write your code here
        
        ResultType result = helper(root);
        return result.maxLength;
    }
    
    public ResultType helper(TreeNode root) {
        
        if (root == null) {
            return new ResultType(0, 0, 0);
        }
        
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        
        int up = 0;
        int down = 0;
        
        if (root.left != null && root.left.val + 1 == root.val) {
            down = Math.max(down, left.maxDown + 1);
        }
        
        if (root.left != null && root.left.val - 1 == root.val) {
            up = Math.max(up, left.maxUp + 1);
        }
        
        if (root.right != null && root.right.val + 1 == root.val) {
            down = Math.max(down, right.maxDown + 1);
        }
        
        if (root.right != null && root.right.val - 1 == root.val) {
            up = Math.max(up, right.maxUp + 1);
        }
        
        int max = Math.max(Math.max(left.maxLength, right.maxLength), up + down + 1);
        return new ResultType(max, up, down);
    }
}