549. Binary Tree Longest Consecutive Sequence II

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input:
        1
       / \
      2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input:
        2
       / \
      1   3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Note: All the values of tree nodes are in the range of [-1e7, 1e7].

利用一個helper function回傳當前node的left/right child形成的連續遞增和遞減序列數量。可能的答案是由每個節點延伸出去最長的遞增和遞減序列數量相加再加上當前的這一個node。

// Bottom Up 
pair<int, int> helper(TreeNode* node, TreeNode* parent, int& res) { 
    if (!node) return {0, 0};
    auto left = helper(node->left, node, res), right = helper(node->right, node, res);
    res = max({res, left.first + right.second + 1, left.second + right.first + 1});
    int inc = 0, dec = 0;
    if (node->val == parent->val + 1)
        inc = max(left.first, right.first) + 1;
    else if (node->val + 1 == parent->val)
        dec = max(left.second, right.second) + 1;
    return {inc, dec};
}
int longestConsecutive(TreeNode* root) { // time: O(n); space: O(n)
    int res = 0;
    helper(root, root, res);
    return res;
}

其實不需要parse整個parent TreeNode而是只需要parent->val就好。

// Bottom Up 
pair<int, int> helper(TreeNode* node, int preVal, int& res) { 
    if (!node) return {0, 0};
    auto left = helper(node->left, node->val, res), right = helper(node->right, node->val, res);
    res = max({res, left.first + right.second + 1, left.second + right.first + 1});
    int inc = 0, dec = 0;
    if (node->val == preVal + 1)
        inc = max(left.first, right.first) + 1;
    if (node->val + 1 == preVal)
        dec = max(left.second, right.second) + 1;
    return {inc, dec};
}
int longestConsecutive(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    int res = 0;
    helper(root, root->val, res);
    return res;
}

298. Binary Tree Longest Consecutive Sequence