Saturday, October 31, 2015

LeetCode [298] Binary Tree Longest Consecutive Sequence

 298. Binary Tree Longest Consecutive Sequence

Medium

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 1:

Input:

   1
    \
     3
    / \
   2   4
        \
         5

Output: 3

Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2:

Input:

   2
    \
     3
    / 
   2    
  / 
 1

Output: 2 

Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//C++: 40ms dfs recursive
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        if(!root) return 0;
        int ret = 1;
        lc(root, ret, root->val, 1);
        return ret;
    }
    void lc(TreeNode* root, int &ret, int parent, int len){
        if(!root) return;
        if(root->val == parent+1){
            ret = max(ret, len+1);
        }else{
            len = 0;            
        }
        lc(root->left, ret, root->val, len+1);
        lc(root->right, ret, root->val, len+1);        
    }
};

//C++: 48ms dfs iterative
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        if(!root) return 0;
        stack<pair<TreeNode*, int>> stk;
        stk.push(pair<TreeNode*, int>(root, 1));
        int ret = 1;
        while(!stk.empty()){
            TreeNode* t = stk.top().first;
            int cur = stk.top().second;
            stk.pop();
            if(t->left){
                if(t->left->val == t->val+1){
                    stk.push(pair<TreeNode*, int>(t->left, cur+1));
                    ret = max(ret, cur+1);
                }else{
                    stk.push(pair<TreeNode*, int>(t->left, 1));
                }
            }
            if(t->right){
                if(t->right->val == t->val+1){
                    stk.push(pair<TreeNode*, int>(t->right, cur+1));
                    ret = max(ret, cur+1);
                }else{
                    stk.push(pair<TreeNode*, int>(t->right, 1));
                }
            }            
        }
        return ret;
    }
};

//C++: 44ms bfs iterative
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        if(!root) return 0;
        queue<pair<TreeNode *, int>> que;
        que.push(pair<TreeNode *, int>(root, 1));
        int ret = 1;
        while(!que.empty()){
            TreeNode * t = que.front().first;
            int cur = que.front().second;
            que.pop();
            if(t->left){
                if(t->left->val == t->val+1){
                    ret = max(ret, cur+1);
                    que.push(pair<TreeNode *, int>(t->left, cur+1));
                }else{
                    que.push(pair<TreeNode *, int>(t->left, 1));
                }
            }
            if(t->right){
                if(t->right->val == t->val+1){
                    ret = max(ret, cur+1);
                    que.push(pair<TreeNode *, int>(t->right, cur+1));
                }else{
                    que.push(pair<TreeNode *, int>(t->right, 1));
                }
            }
        }
        return ret;
    }
};
Posted by at
Labels: , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)