Binary Tree Longest Consecutive Sequence

https://leetcode.com/problems/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).

Thoughts

分治得到左子树中的最长和右子树的最长, 由于子树中的最长未必穿过左/右儿子但当前结点可能和左右儿子形成新的最长, 因此还要记录穿过当前节点最长. 有两种记录的方法, 一种bottom-up, 还有种up-bottom, 后者不需要全局变量.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private 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);
    }

    public int longestConsecutive(TreeNode root) {
        return helper(root, 0, root == null ? 0 : root.val);
    }
}

Analysis

时间复杂度O(N).