# DFS C++, Python solutions

• c++ solution:

``````class Solution {
public:
int longestConsecutive(TreeNode* root) {
int longest = 0;
dfs(root, root, longest);
return longest;
}

pair<int, int> dfs(TreeNode * node, TreeNode * parent, int & longest) {
if ( NULL == node ) {
return make_pair(0, 0);
}
auto left = dfs(node->left, node, longest);
auto right = dfs(node->right, node, longest);
longest = max(longest, left.first + right.second + 1);
longest = max(longest, left.second + right.first + 1);
int inc = 0, dec = 0;
if ( node->val == parent->val + 1 ) {
inc = max(left.first, right.first) + 1;
}
if ( node->val == parent->val - 1 ) {
dec = max(left.second, right.second) + 1;
}
return make_pair(inc, dec);
}
};
``````

python solution

``````class Solution(object):
def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(node, parent):
if not node:
return 0, 0
li, ld = dfs(node.left, node)
ri, rd = dfs(node.right, node)
l[0] = max(l[0], li + rd + 1, ld + ri + 1)
if node.val == parent.val + 1:
return max(li, ri) + 1, 0
if node.val == parent.val - 1:
return 0, max(ld, rd) + 1
return 0, 0
l = [0]
dfs(root, root)
return l[0]
``````

• Why'd you use a list when you're just storing one number (python solution)?

• Why'd you use a list when you're just storing one number (python solution)?

It's just a trick, because I need to modify it in inner scope.

• @zqfan Can't use a global variable or something? I feel like there must be another way other than creating a list.

• @zqfan Can't use a global variable or something? I feel like there must be another way other than creating a list.

of course you can use global variables, or if you are using py3, you can use nonlocal keyword instead of global variables.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.