Skip to content

549. Binary Tree Longest Consecutive Sequence II 👍

  • Time: $O(n)$
  • Space: $O(h)$
 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
struct T {
  int inc;  // the length of longest incrementing branch
  int dec;  // the length of longest decrementing branch
};

class Solution {
 public:
  int longestConsecutive(TreeNode* root) {
    int ans = 0;
    longestPath(root, ans);
    return ans;
  }

 private:
  T longestPath(TreeNode* root, int& ans) {
    if (root == nullptr)
      return {0, 0};

    int inc = 1;
    int dec = 1;

    if (root->left) {
      T l = longestPath(root->left, ans);
      if (root->val + 1 == root->left->val)
        inc = l.inc + 1;
      else if (root->val - 1 == root->left->val)
        dec = l.dec + 1;
    }

    if (root->right) {
      T r = longestPath(root->right, ans);
      if (root->val + 1 == root->right->val)
        inc = max(inc, r.inc + 1);
      else if (root->val - 1 == root->right->val)
        dec = max(dec, r.dec + 1);
    }

    ans = max(ans, inc + dec - 1);
    return {inc, dec};
  }
};

 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
class T {
  public int inc; // the length of longest incrementing branch
  public int dec; // the length of longest decrementing branch

  public T(int inc, int dec) {
    this.inc = inc;
    this.dec = dec;
  }
}

class Solution {
  public int longestConsecutive(TreeNode root) {
    longestPath(root);
    return ans;
  }

  private int ans = 0;

  private T longestPath(TreeNode root) {
    if (root == null)
      return new T(0, 0);

    int inc = 1;
    int dec = 1;

    if (root.left != null) {
      T l = longestPath(root.left);
      if (root.val + 1 == root.left.val)
        inc = l.inc + 1;
      else if (root.val - 1 == root.left.val)
        dec = l.dec + 1;
    }

    if (root.right != null) {
      T r = longestPath(root.right);
      if (root.val + 1 == root.right.val)
        inc = Math.max(inc, r.inc + 1);
      else if (root.val - 1 == root.right.val)
        dec = Math.max(dec, r.dec + 1);
    }

    ans = Math.max(ans, inc + dec - 1);
    return new T(inc, dec);
  }
}