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. --- .../01_binary_tree_inorder_traversal.cc | 27 +++++++++++ .../02_binary_tree_zigzag_level_order_traversal.cc | 53 ++++++++++++++++++++++ ...ary_tree_from_preorder_and_inorder_traversal.cc | 49 ++++++++++++++++++++ ..._populating_next_right_pointers_in_each_node.cc | 47 +++++++++++++++++++ 4 files changed, 176 insertions(+) create mode 100644 top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.cc create mode 100644 top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc create mode 100644 top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc create mode 100644 top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc (limited to 'top-interview-questions/medium') diff --git a/top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.cc b/top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.cc new file mode 100644 index 0000000..6a2762b --- /dev/null +++ b/top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.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: + void inorder(TreeNode* node, vector& vals) { + if (node == nullptr) return; + + inorder(node->left, vals); + vals.push_back(node->val); + inorder(node->right, vals); + } + + vector inorderTraversal(TreeNode* root) { + vector vals; + inorder(root, vals); + return vals; + } +}; diff --git a/top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc b/top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc new file mode 100644 index 0000000..2abb093 --- /dev/null +++ b/top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc @@ -0,0 +1,53 @@ +/** + * 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 push(vector& level, vector& values, const TreeNode* node) { + level.push_back(node); + values.push_back(node->val); + } + + void zigZag(bool leftRight, const vector& level, vector>& values) { + vector next_level; + vector next_values; + + if (leftRight) { + for (int i = level.size()-1; i >= 0; --i) { + const TreeNode* node = level[i]; + if (node->left) push(next_level, next_values, node->left); + if (node->right) push(next_level, next_values, node->right); + } + } + else { + for (int i = level.size()-1; i >= 0; --i) { + const TreeNode* node = level[i]; + if (node->right) push(next_level, next_values, node->right); + if (node->left) push(next_level, next_values, node->left); + } + } + + if (!next_level.empty()) { + values.push_back(next_values); + zigZag(!leftRight, next_level, values); + } + } + + vector> zigzagLevelOrder(TreeNode* root) { + if (root == nullptr) return {}; + + vector level = {root}; + vector> values = {{root->val}}; + + zigZag(false, level, values); + return values; + } +}; diff --git a/top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc b/top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc new file mode 100644 index 0000000..95e3655 --- /dev/null +++ b/top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc @@ -0,0 +1,49 @@ +/** + * 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: + TreeNode* build(const vector& preorder, const vector& inorder, + int& preIdx, int leftIdx, int rightIdx) { + // Base case. + if (leftIdx > rightIdx) { + return nullptr; + } + + // Root value. + const int root = preorder[preIdx++]; + + // Base case. + if (leftIdx == rightIdx) { + return new TreeNode{root, nullptr, nullptr}; + } + // Recursive case. + else { + // Find the root in the inorder array. + int inorderRootIdx = -1; + for (int i = 0; i < inorder.size(); ++i) { + if (inorder[i] == root) { + inorderRootIdx = i; + break; + } + } + // Build recursively. + TreeNode* left = build(preorder, inorder, preIdx, leftIdx, inorderRootIdx-1); + TreeNode* right = build(preorder, inorder, preIdx, inorderRootIdx+1, rightIdx); + return new TreeNode{root, left, right}; + } + } + + TreeNode* buildTree(vector& preorder, vector& inorder) { + int preIdx = 0; + return build(preorder, inorder, preIdx, 0, preorder.size()-1); + } +}; diff --git a/top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc b/top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc new file mode 100644 index 0000000..17a5874 --- /dev/null +++ b/top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc @@ -0,0 +1,47 @@ +/* +// Definition for a Node. +class Node { +public: + int val; + Node* left; + Node* right; + Node* next; + + Node() : val(0), left(NULL), right(NULL), next(NULL) {} + + Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} + + Node(int _val, Node* _left, Node* _right, Node* _next) + : val(_val), left(_left), right(_right), next(_next) {} +}; +*/ + +class Solution { +public: + // The obvious solution is to do a BFS and connect the nodes in each level. + // However, the problem asks us to use "constant space" (depth of tree). + + void connectLeftRight(Node* leftTree, Node* rightTree) { + while (leftTree && rightTree) { + leftTree->next = rightTree; + + leftTree = leftTree->right; + rightTree = rightTree->left; + } + } + + Node* connect(Node* root) { + if (root == nullptr) { + return root; + } + + connect(root->left); + connect(root->right); + + if (root->left) { // Non-leaf node. + connectLeftRight(root->left, root->right); + } + + return root; + } +}; -- cgit v1.2.3