549 Binary Tree Longest Consecutive Sequence II

Description

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].

Note

Partial Right Solution

dfs,

1. left decrease + right increase
2. left increase + right decrease
3. max of case 1 , case 2

Correct Solution

Also need to consider one more senarios:

1. calculate the max inc & max dec for sub nodes

2. calculate the inc & dec of current node (using the result from sub nodes)

Code

class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        int rst = 0;
        dfs(root, root, rst);
        return rst;
    }
private:
    pair<int, int> dfs(TreeNode* node, TreeNode* next, int &rst) {
        if(node == nullptr || next == nullptr) {
            return make_pair(0,0);
        }

        auto left = dfs(next, next->left, rst);
        auto right = dfs(next, next->right, rst);

        rst = max(rst, left.first + right.second + 1);
        rst = max(rst, left.second + right.first + 1);

        int inc = 0, dec = 0;
        if(node->val + 1 == next->val) {
            inc = max(left.first, right.first) + 1;
        }
        else if(node->val - 1 == next->val) {
            dec = max(left.second, right.second) + 1;
        }

        return make_pair(inc, dec);
    }
};