---
tags: leetcode
---

# [298. Binary Tree Longest Consecutive Sequence](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence)
---
# My Solution
## Solution 1
### The Key Idea for Solving This Coding Question
DFS, recursion, post-order traversal
`dfs` 傳回由 `root` ( `dfs` 的 parameter) 到 `root` 其中一個子節點的 consecutive sequence path 的長度。
### C++ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int longestConsecutive(TreeNode *root) {
        int longest = 1;

        dfs(root, longest);
        return longest;
    }

private:
    // dfs returns the consecutive length from root
    // to one of its descendants.
    int dfs(TreeNode *root, int &longest) {
        if (root == nullptr) {
            return 0;
        }

        int leftLen = 1;
        if (root->left != nullptr) {
            leftLen = dfs(root->left, longest);
            if (root->val + 1 == root->left->val) {
                ++leftLen;
            } else {
                leftLen = 1;
            }
        }

        int rightLen = 1;
        if (root->right != nullptr) {
            rightLen = dfs(root->right, longest);
            if (root->val + 1 == root->right->val) {
                ++rightLen;
            } else {
                rightLen = 1;
            }
        }

        int max1 = max(leftLen, rightLen);
        longest = max(longest, max1);

        return max1;
    }
};

### Time Complexity
$O(n)$
$n$ is the number of nodes in the binary tree referred by `root`.
### Space Complexity
$O(H)$
$H$ is the height of the binary tree referred by `root`.
## Solution 2
### The Key Idea for Solving This Coding Question
DFS, recursion, post-order traversal
`dfs` 傳回由 `root` ( `dfs` 的第二個 parameter) 的父節點 `parent` ( `dfs` 的第一個 parameter) 到 `root` 其中一個子節點的 consecutive sequence path 的長度。
### C++ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

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

private:
    int dfs(TreeNode *parent, TreeNode *root, int &longest) {
        if (root == nullptr) {
            return 1;
        }
        
        int leftLen = dfs(root, root->left, longest);
        int rightLen = dfs(root, root->right, longest);
        int localMaxLen = max(leftLen, rightLen);
        
        if (parent != nullptr) {
            if (parent->val + 1 == root->val) {
                ++localMaxLen;
            } else {
                localMaxLen = 1;
            }
            longest = max(longest, localMaxLen);
            return localMaxLen;
        }
        
        longest = max(longest, localMaxLen);
        return localMaxLen;
    }
};

## Time Complexity
$O(n)$
$n$ is the number of nodes in the binary tree referred by `root`.
## Space Complexity
$O(H)$
$H$ is the height of the binary tree referred by `root`.
# Miscellaneous
[549. Binary Tree Longest Consecutive Sequence II](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/)