From 4689e4e80b479be25f7557d05818f5caa723aafa Mon Sep 17 00:00:00 2001 From: 3gg <3gg@shellblade.net> Date: Wed, 5 Feb 2025 18:36:31 -0800 Subject: Initial commit. --- .../easy/trees/01_maximum_depth_of_binary_tree.cc | 20 ++++++++ .../easy/trees/02_valid_binary_search_tree.cc | 54 ++++++++++++++++++++++ .../easy/trees/03_symmetric_tree.cc | 52 +++++++++++++++++++++ .../trees/04_binary_tree_level_order_traversal.cc | 44 ++++++++++++++++++ ...5_convert_sorted_array_to_binary_search_tree.cc | 27 +++++++++++ 5 files changed, 197 insertions(+) create mode 100644 top-interview-questions/easy/trees/01_maximum_depth_of_binary_tree.cc create mode 100644 top-interview-questions/easy/trees/02_valid_binary_search_tree.cc create mode 100644 top-interview-questions/easy/trees/03_symmetric_tree.cc create mode 100644 top-interview-questions/easy/trees/04_binary_tree_level_order_traversal.cc create mode 100644 top-interview-questions/easy/trees/05_convert_sorted_array_to_binary_search_tree.cc (limited to 'top-interview-questions/easy/trees') diff --git a/top-interview-questions/easy/trees/01_maximum_depth_of_binary_tree.cc b/top-interview-questions/easy/trees/01_maximum_depth_of_binary_tree.cc new file mode 100644 index 0000000..4d13af7 --- /dev/null +++ b/top-interview-questions/easy/trees/01_maximum_depth_of_binary_tree.cc @@ -0,0 +1,20 @@ +/** + * 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 max(int a, int b) { return a > b ? a : b; } + + int maxDepth(TreeNode* root) { + if (!root) return 0; + return 1 + max(maxDepth(root->left), maxDepth(root->right)); + } +}; diff --git a/top-interview-questions/easy/trees/02_valid_binary_search_tree.cc b/top-interview-questions/easy/trees/02_valid_binary_search_tree.cc new file mode 100644 index 0000000..a071daf --- /dev/null +++ b/top-interview-questions/easy/trees/02_valid_binary_search_tree.cc @@ -0,0 +1,54 @@ +/** + * 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: + bool isValidBSTRec(TreeNode* root, int* min, int* max) { + if (root->left && root->right) { + int leftMin, leftMax, rightMin, rightMax; + if (!isValidBSTRec(root->left, &leftMin, &leftMax) || + !isValidBSTRec(root->right, &rightMin, &rightMax)) { + return false; + } + *min = std::min(std::min(leftMin, rightMin), root->val); + *max = std::max(std::max(leftMax, rightMax), root->val); + return (leftMax < root->val) && (root->val < rightMin); + } + else if (root->left) { + int leftMin, leftMax; + if (!isValidBSTRec(root->left, &leftMin, &leftMax)) { + return false; + } + *min = std::min(leftMin, root->val); + *max = std::max(leftMax, root->val); + return (leftMax < root->val); + } + else if (root->right) { + int rightMin, rightMax; + if (!isValidBSTRec(root->right, &rightMin, &rightMax)) { + return false; + } + *min = std::min(rightMin, root->val); + *max = std::max(rightMax, root->val); + return (root->val < rightMin); + } + else { + *min = *max = root->val; + return true; + } + } + + bool isValidBST(TreeNode* root) { + if (!root) return true; + int minVal, maxVal; + return isValidBSTRec(root, &minVal, &maxVal); + } +}; diff --git a/top-interview-questions/easy/trees/03_symmetric_tree.cc b/top-interview-questions/easy/trees/03_symmetric_tree.cc new file mode 100644 index 0000000..bbdc52b --- /dev/null +++ b/top-interview-questions/easy/trees/03_symmetric_tree.cc @@ -0,0 +1,52 @@ +/** + * 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: + bool isSymmetricVector(const std::vector& nodes) { + if (nodes.empty()) return true; + if (nodes.size() == 1) return true; + for (size_t i = 0; i < nodes.size()/2; ++i) { + const size_t j = nodes.size() - i - 1; + if ((nodes[i] && !nodes[j]) || + (!nodes[i] && nodes[j]) || + (nodes[i] && nodes[j] && (nodes[i]->val != nodes[j]->val))) { + return false; + } + } + return true; + } + + bool isSymmetricBfs(std::vector& current_level, + std::vector& next_level) { + if (current_level.empty()) { + return true; + } + if (!isSymmetricVector(current_level)) { + return false; + } + for (const TreeNode* node : current_level) { + if (node) { + next_level.push_back(node->left); + next_level.push_back(node->right); + } + } + current_level.clear(); // New next level. + return isSymmetricBfs(next_level, current_level); + } + + bool isSymmetric(TreeNode* root) { + if (!root) return true; + std::vector current_level({root}); + std::vector next_level; + return isSymmetricBfs(current_level, next_level); + } +}; diff --git a/top-interview-questions/easy/trees/04_binary_tree_level_order_traversal.cc b/top-interview-questions/easy/trees/04_binary_tree_level_order_traversal.cc new file mode 100644 index 0000000..9c506ab --- /dev/null +++ b/top-interview-questions/easy/trees/04_binary_tree_level_order_traversal.cc @@ -0,0 +1,44 @@ +/** + * 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: + void bfs(vector>& levels, + vector& current_level, + vector& next_level) { + if (current_level.empty()) { + return; + } + levels.push_back({}); + vector& level = levels.back(); + level.reserve(current_level.size()); + for (const TreeNode* node : current_level) { + level.push_back(node->val); + if (node->left) { + next_level.push_back(node->left); + } + if (node->right) { + next_level.push_back(node->right); + } + } + current_level.clear(); // New next level. + bfs(levels, next_level, current_level); + } + + vector> levelOrder(TreeNode* root) { + if (!root) return {}; + vector> levels; + vector current_level({root}); + vector next_level; + bfs(levels, current_level, next_level); + return levels; + } +}; diff --git a/top-interview-questions/easy/trees/05_convert_sorted_array_to_binary_search_tree.cc b/top-interview-questions/easy/trees/05_convert_sorted_array_to_binary_search_tree.cc new file mode 100644 index 0000000..4882a2a --- /dev/null +++ b/top-interview-questions/easy/trees/05_convert_sorted_array_to_binary_search_tree.cc @@ -0,0 +1,27 @@ +/** + * 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: + // 'end' is one past the end. + TreeNode* makeTree(const vector& nums, size_t start, size_t end) { + if (start >= end) return nullptr; + const size_t middle = start + (end - start) / 2; + TreeNode* root = new TreeNode(nums[middle]); + root->left = makeTree(nums, start, middle); + root->right = makeTree(nums, middle+1, end); + return root; + } + + TreeNode* sortedArrayToBST(vector& nums) { + return makeTree(nums, 0, nums.size()); + } +}; -- cgit v1.2.3