• Time:O(n)
• Space:O(h)

## C++

``````struct T {
int inc;  // length of longest incrementing branch
int dec;  // length of longest decrementing branch
};

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

private:
// return (longest increment, longest decrement)
T longestPath(TreeNode* root, int& ans) {
if (!root)
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};
}
};
``````

## JAVA

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

// return (longest increment, longest decrement)
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);
}
}
``````