commit 66a48a2b8d4d2f097dd4bc313aeea5ba7c1d7c45
parent 4a4aabf9af32c9c11e623dd56367ef38ba55c08e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sun, 1 Jan 2023 22:42:34 +0100
Some Tree Problems
Diffstat:
7 files changed, 168 insertions(+), 1 deletion(-)
diff --git a/Problems/0110.cpp b/Problems/0110.cpp
@@ -0,0 +1,23 @@
+class Solution {
+public:
+ bool isBalanced(TreeNode *root) {
+ if (!root) return true;
+ stack<TreeNode *> st;
+ st.push(root);
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ if (root == nullptr) {
+ st.pop(), root = st.top(), st.pop();
+ int left = root->left ? root->left->val : 0;
+ int right = root->right ? root->right->val : 0;
+ if (abs(right - left) > 1) return false;
+ root->val = max(left, right) + 1;
+ continue;
+ }
+ st.push(nullptr);
+ if (root->left) st.push(root->left);
+ if (root->right) st.push(root->right);
+ }
+ return true;
+ }
+};
diff --git a/Problems/0654.cpp b/Problems/0654.cpp
@@ -0,0 +1,33 @@
+class Solution {
+ struct record {
+ TreeNode **parent;
+ int start, end;
+ record(TreeNode **p, int s, int e) : parent(p), start(s), end(e) {}
+ };
+
+public:
+ TreeNode *constructMaximumBinaryTree(vector<int> &nums) {
+ TreeNode *head, tmp;
+ stack<record> st;
+
+ head = new TreeNode(-1);
+ st.push({&head->right, 0, (int)nums.size()});
+ while (!st.empty()) {
+ auto [root, start, end] = st.top();
+ st.pop();
+ while (start < end) {
+ int index = -1;
+ for (int i = start, maxi = INT_MIN; i < end; i++)
+ if (nums[i] > maxi) {
+ maxi = nums[i];
+ index = i;
+ }
+ *root = new TreeNode(nums[index]);
+ st.push({&(*root)->left, start, index});
+ root = &(*root)->right;
+ start = index + 1;
+ }
+ }
+ return head->right;
+ }
+};
diff --git a/Problems/0671.cpp b/Problems/0671.cpp
@@ -0,0 +1,21 @@
+class Solution {
+public:
+ int findSecondMinimumValue(TreeNode *root) {
+ if (!root) return -1;
+ int val = root->val;
+ long long res = LONG_MAX;
+ stack<TreeNode *> st;
+ st.push(root);
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ st.pop();
+ if (!root->left) continue;
+ int m = max(root->left->val, root->right->val);
+ if (m != val) res = min(res, (long long)m);
+ if (root->left->val == val) st.push(root->left);
+ if (root->right->val == val) st.push(root->right);
+ }
+
+ return res != LONG_MAX ? res : -1;
+ }
+};
diff --git a/Problems/1302.cpp b/Problems/1302.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+ int deepestLeavesSum(TreeNode *root) {
+ int sum = 0;
+
+ queue<TreeNode *> q;
+ q.push(root);
+ while (!q.empty()) {
+ sum = 0;
+ for (int k = q.size(); k > 0; k--) {
+ TreeNode *root = q.front();
+ q.pop();
+ sum += root->val;
+ if (root->left) q.push(root->left);
+ if (root->right) q.push(root->right);
+ }
+ }
+ return sum;
+ }
+};
diff --git a/Problems/1315.cpp b/Problems/1315.cpp
@@ -0,0 +1,31 @@
+class Solution {
+public:
+ int sumEvenGrandparent(TreeNode *root) {
+ stack<TreeNode *> st;
+ int sum = 0;
+
+ st.push(root);
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ st.pop();
+
+ if (root->left) {
+ st.push(root->left);
+ if (root->val % 2 == 0) {
+ if (root->left->left) sum += root->left->left->val;
+ if (root->left->right) sum += root->left->right->val;
+ }
+ }
+
+ if (root->right) {
+ st.push(root->right);
+ if (root->val % 2 == 0) {
+ if (root->right->left) sum += root->right->left->val;
+ if (root->right->right) sum += root->right->right->val;
+ }
+ }
+ }
+
+ return sum;
+ }
+};
diff --git a/Problems/2265.cpp b/Problems/2265.cpp
@@ -0,0 +1,33 @@
+class Solution {
+public:
+ int averageOfSubtree(TreeNode *root) {
+ stack<TreeNode *> st;
+ unordered_map<TreeNode *, int> um;
+ int res = 0;
+
+ st.push(root);
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ if (root == nullptr) {
+ st.pop(), root = st.top(), st.pop();
+ int sum = root->val, count = 1;
+ if (root->left) {
+ sum += root->left->val;
+ count += um[root->left];
+ }
+ if (root->right) {
+ sum += root->right->val;
+ count += um[root->right];
+ }
+ if (root->val == sum / count) res++;
+ um[root] = count;
+ root->val = sum;
+ continue;
+ }
+ st.push(nullptr);
+ if (root->left) st.push(root->left);
+ if (root->right) st.push(root->right);
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -48,6 +48,7 @@ if you have any questions.
| 0107 | Medium | [Binary Tree Level Order Traversal II](Problems/0107.cpp) |
| 0108 | Easy | [Convert Sorted Array to Binary Search Tree](Problems/0108.cpp) |
| 0109 | Medium | [Convert Sorted List to Binary Search Tree](Problems/0109.cpp) |
+| 0110 | Easy | [Balanced Binary Tree](Problems/0110.cpp) |
| 0111 | Easy | [Minimum Depth of Binary Tree](Problems/0111.cpp) |
| 0112 | Easy | [Path Sum](Problems/0112.cpp) |
| 0114 | Medium | [Flatten Binary Tree to Linked List](Problems/0114.cpp) |
@@ -94,6 +95,7 @@ if you have any questions.
| 0283 | Easy | [Move Zeroes](Problems/0283.cpp) |
| 0287 | Medium | [Find the Duplicate Number](Problems/0287.cpp) |
| 0290 | Easy | [Word Pattern](Problems/0290.cpp) |
+| 0295 | Hard | [Find Median from Data Stream](Problems/0295.cpp) |
| 0328 | Medium | [Odd Even Linked List](Problems/0328.cpp) |
| 0338 | Easy | [Counting Bits](Problems/0338.cpp) |
| 0344 | Easy | [Reverse String](Problems/0344.cpp) |
@@ -137,7 +139,9 @@ if you have any questions.
| 0617 | Easy | [Merge Two Binary Trees](Problems/0617.cpp) |
| 0637 | Easy | [Average of Levels in Binary Tree](Problems/0637.cpp) |
| 0653 | Easy | [Two Sum IV - Input is a BST](Problems/0653.cpp) |
+| 0654 | Medium | [Maximum Binary Tree](Problems/0654.cpp) |
| 0669 | Medium | [Trim a Binary Search Tree](Problems/0669.cpp) |
+| 0671 | Easy | [Second Minimum Node In a Binary Tree](Problems/0671.cpp) |
| 0684 | Medium | [Redundant Connection](Problems/0684.cpp) |
| 0700 | Easy | [Search in a Binary Search Tree](Problems/0700.cpp) |
| 0701 | Medium | [Insert into a Binary Search Tree](Problems/0701.cpp) |
@@ -186,7 +190,9 @@ if you have any questions.
| 1137 | Easy | [N-th Tribonacci Number](Problems/1137.cpp) |
| 1209 | Medium | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp) |
| 1290 | Easy | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp) |
+| 1302 | Medium | [Deepest Leaves Sum](Problems/1302.cpp) |
| 1305 | Medium | [All Elements in Two Binary Search Trees](Problems/1305.cpp) |
+| 1315 | Medium | [Sum of Nodes with Even-Valued Grandparent](Problems/1315.cpp) |
| 1319 | Medium | [Number of Operations to Make Network Connected](Problems/1319.cpp) |
| 1323 | Easy | [Maximum 69 Number](Problems/1323.cpp) |
| 1337 | Easy | [The K Weakest Rows in a Matrix](Problems/1337.cpp) |
@@ -225,6 +231,7 @@ if you have any questions.
| 2181 | Medium | [Merge Nodes in Between Zeros](Problems/2181.cpp) |
| 2235 | Easy | [Add Two Integers](Problems/2235.cpp) |
| 2236 | Easy | [Root Equals Sum of Children](Problems/2236.cpp) |
+| 2265 | Medium | [Count Nodes Equal to Average of Subtree](Problems/2265.cpp) |
| 2279 | Medium | [Maximum Bags With Full Capacity of Rocks](Problems/2279.cpp) |
| 2285 | Medium | [Maximum Total Importance of Roads](Problems/2285.cpp) |
| 2326 | Medium | [Spiral Matrix IV](Problems/2326.cpp) |
@@ -234,7 +241,6 @@ if you have any questions.
| 2465 | Easy | [Number of Distinct Averages](Problems/2465.cpp) |
| 2466 | Medium | [Count Ways To Build Good Strings](Problems/2466.cpp) |
| 2467 | Medium | [Most Profitable Path in a Tree](Problems/2467.cpp) |
-| 2469 | Hard | [Find Median from Data Stream](Problems/0295.cpp) |
## DNF
