[549. Binary Tree Longest Consecutive Sequence II](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/)

--- tags: leetcode --- # [549. Binary Tree Longest Consecutive Sequence II](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/) --- # My Solution ## The Key Idea for Solving This Coding Question DFS, recursion, postorder traversal ## C++ Code 1 ```cpp= /** * 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) {} * }; */ struct LenData { int incLen; int decLen; LenData(int incLen, int decLen) : incLen(incLen), decLen(decLen) {} }; class Solution { public: int longestConsecutive(TreeNode *root) { int longest = 0; dfs(root, longest); return longest; } private: LenData dfs(TreeNode *root, int &longest) { if (root == nullptr) { return LenData(0, 0); } int incLen = 1, decLen = 1; if (root->left != nullptr) { LenData leftData = dfs(root->left, longest); if (root->val + 1 == root->left->val) { leftData.incLen += 1; } else { leftData.incLen = 1; } if (root->val == root->left->val + 1) { leftData.decLen += 1; } else { leftData.decLen = 1; } incLen = max(incLen, leftData.incLen); decLen = max(decLen, leftData.decLen); } if (root->right != nullptr) { LenData rightData = dfs(root->right, longest); if (root->val + 1 == root->right->val) { rightData.incLen += 1; } else { rightData.incLen = 1; } if (root->val == root->right->val + 1) { rightData.decLen += 1; } else { rightData.decLen = 1; } incLen = max(incLen, rightData.incLen); decLen = max(decLen, rightData.decLen); } longest = max(longest, incLen + decLen - 1); return LenData(incLen, decLen); } }; ``` :::spoiler Code 1 的第二種寫法 ```cpp= /** * 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) {} * }; */ struct lenData { int incLen; int decLen; lenData(int incLen, int decLen) : incLen(incLen), decLen(decLen) {} }; class Solution { public: int longestConsecutive(TreeNode *root) { int longest = 0; dfs(root, longest); return longest; } private: lenData dfs(TreeNode *root, int &longest) { if (root == nullptr) { return lenData(0, 0); } int incLen = 1, decLen = 1; if (root->left != nullptr) { lenData leftLen = dfs(root->left, longest); if (root->val == root->left->val + 1) { decLen = max(decLen, leftLen.decLen + 1); } else if (root->val + 1 == root->left->val) { incLen = max(incLen, leftLen.incLen + 1); } } if (root->right != nullptr) { lenData rightLen = dfs(root->right, longest); if (root->val == root->right->val + 1) { decLen = max(decLen, rightLen.decLen + 1); } else if (root->val + 1 == root->right->val) { incLen = max(incLen, rightLen.incLen + 1); } } longest = max(longest, incLen + decLen - 1); return lenData(incLen, decLen); } }; ``` ::: ## C++ Code 2 ```cpp= /** * 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) {} * }; */ struct lenData { int incLen; int decLen; lenData(int incLen, int decLen) : incLen(incLen), decLen(decLen) {} }; class Solution { public: int longestConsecutive(TreeNode *root) { int longest = 1; dfs(nullptr, root, longest); return longest; } private: // dfs returns the increasing and descreasing consequtive length // from the parent of root. lenData dfs(TreeNode *parent, TreeNode *root, int &longest) { if (root == nullptr) { return lenData(1, 1); } lenData leftData = dfs(root, root->left, longest); lenData rightData = dfs(root, root->right, longest); int incLen = max(leftData.incLen, rightData.incLen); int decLen = max(leftData.decLen, rightData.decLen); longest = max(longest, incLen + decLen - 1); if (parent != nullptr) { if (parent->val + 1 == root->val) { int max1 = max(incLen + 1, incLen + decLen - 1); longest = max(longest, max1); return lenData(incLen + 1, 1); } if (parent->val == root->val + 1) { int max2 = max(decLen +1, incLen + decLen - 1); longest = max(longest, max2); return lenData(1, decLen + 1); } return lenData(1, 1); } return lenData(incLen, decLen); } }; ``` :::spoiler Code 2 的第二種寫法 ```cpp= /** * 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) {} * }; */ struct lenData { int incLen; int decLen; lenData(int incLen, int decLen) : incLen(incLen), decLen(decLen) {} }; class Solution { public: int longestConsecutive(TreeNode *root) { int longest = 1; dfs(nullptr, root, longest); return longest; } private: // dfs returns the increasing and descreasing consequtive length // from the parent of root. lenData dfs(TreeNode *parent, TreeNode *root, int &longest) { if (root == nullptr) { return lenData(1, 1); } lenData leftData = dfs(root, root->left, longest); lenData rightData = dfs(root, root->right, longest); int incLen = max(leftData.incLen, rightData.incLen); int decLen = max(leftData.decLen, rightData.decLen); longest = max(longest, incLen + decLen - 1); if (parent != nullptr) { if (parent->val + 1 == root->val) { int max1 = max(incLen + 1, incLen + decLen - 1); longest = max(longest, max1); return lenData(incLen + 1, 1); } if (parent->val == root->val + 1) { int max2 = max(decLen +1, incLen + decLen - 1); longest = max(longest, max2); return lenData(1, decLen + 1); } return lenData(1, 1); } return lenData(incLen, decLen); } }; ``` ::: ## 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 [298. Binary Tree Longest Consecutive Sequence](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence)