aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--misc.cpp20
-rw-r--r--vertical_order_bst.c103
-rw-r--r--vertical_order_bst.py56
3 files changed, 159 insertions, 20 deletions
diff --git a/misc.cpp b/misc.cpp
deleted file mode 100644
index 8263244..0000000
--- a/misc.cpp
+++ /dev/null
@@ -1,20 +0,0 @@
-class Solution {
-public:
- vector<string> removeSubfolders(vector<string> &folder) {
- sort(folder.begin(), folder.end());
- vector<string> res;
-
- for (auto s : folder) {
- if (res.size() == 0) {
- res.push_back(s);
- continue;
- }
-
- string parent = res[res.size() - 1];
- if (s.substr(0, parent.size() + 1) != parent + '/')
- res.push_back(s);
- }
-
- return res;
- }
-};
diff --git a/vertical_order_bst.c b/vertical_order_bst.c
new file mode 100644
index 0000000..6f6e221
--- /dev/null
+++ b/vertical_order_bst.c
@@ -0,0 +1,103 @@
+// 987. Vertical Order Traversal of a Binary Tree
+#include "leetcode.h"
+
+/*
+ * given the 'root' of a binary tree, calcuate the vertical order traversal of
+ * the binary tree. for each node at position '(row, col)', its left and right
+ * children will be at positions '(row + 1, col - 1)' and '(row + 1, col + 1)'
+ * respectively. the root of the tree is at '(0, 0)'. the vertical order
+ * traversal of a binary tree is a list of top to bottom ordering for each
+ * column index starting from the leftmost column and ending on the rightmost
+ * column. there may be multiple nodes in the same row and same column. in such
+ * a case, sort these nodes by their values. return the vertical order traversal
+ * of the binary tree
+ */
+
+struct value {
+ int row;
+ int col;
+ int val;
+};
+
+int value_cmp(const void *left, const void *right) {
+ const struct value *l = (const struct value *)left;
+ const struct value *r = (const struct value *)right;
+ return l->col < r->col ? -1 : 1;
+ return l->row < r->row ? -1 : 1;
+ return l->val - r->val;
+}
+
+void helper(struct TreeNode *root, int row, int col, struct value **values,
+ size_t *values_size, size_t *values_cap) {
+ if (root) {
+ if (*values_size == *values_cap) {
+ *values_cap = (*values_cap) ? *values_cap * 2 : 16;
+ *values =
+ (struct value *)realloc(*values, *values_cap * sizeof(struct value));
+ }
+ (*values)[(*values_size)].col = col;
+ (*values)[(*values_size)].row = row;
+ (*values)[(*values_size)].val = root->val;
+ ++*values_size;
+ helper(root->left, row + 1, col - 1, values, values_size, values_cap);
+ helper(root->right, row + 1, col + 1, values, values_size, values_cap);
+ }
+}
+
+int **verticalTraversal(struct TreeNode *root, int *returnSize,
+ int **returnColumnSizes) {
+ struct value *v = NULL;
+ size_t values_size = 0, values_cap = 0;
+ helper(root, 0, 0, &v, &values_size, &values_cap);
+ qsort(v, values_size, sizeof(struct value), &value_cmp);
+ int **ans = NULL;
+ *returnColumnSizes = NULL;
+ *returnSize = -1;
+ size_t cap = 0, sub_cap = 0;
+ int prev_col = INT_MIN;
+ for (size_t i = 0; i < values_size; ++i) {
+ if (v[i].col != prev_col) {
+ ++(*returnSize);
+ if (*returnSize == cap) {
+ cap = cap ? cap * 2 : 4;
+ ans = (int **)realloc(ans, cap * sizeof(int *));
+ *returnColumnSizes =
+ (int *)realloc(*returnColumnSizes, cap * sizeof(int));
+ }
+ ans[*returnSize] = NULL;
+ (*returnColumnSizes)[(*returnSize)] = 0;
+ sub_cap = 0;
+ prev_col = v[i].col;
+ }
+ if ((*returnColumnSizes)[*returnSize] == sub_cap) {
+ sub_cap = sub_cap ? sub_cap * 2 : 4;
+ ans[*returnSize] =
+ (int *)realloc(ans[*returnSize], sub_cap * sizeof(int));
+ }
+ ans[*returnSize][(*returnColumnSizes)[*returnSize]++] = v[i].val;
+ }
+ ++(*returnSize);
+ free(v);
+ return ans;
+}
+
+int main() {
+ struct TreeNode *root = treenode_create(1);
+ root->left = treenode_create(2);
+ root->right = treenode_create(3);
+ root->left->left = treenode_create(4);
+ root->left->right = treenode_create(5);
+ root->right->left = treenode_create(6);
+ root->right->right = treenode_create(7);
+ int returnSize, *returnColumnSizes;
+ int **vt = verticalTraversal(root, &returnSize, &returnColumnSizes);
+ for (int i = 0; i < returnSize; i++) {
+ for (int j = 0; j < returnColumnSizes[i]; j++)
+ printf("%d ", vt[i][j]); // expect: [[4],[2],[1,5,6],[3],[7]]
+ printf("\n");
+ }
+ for (int i = 0; i < returnSize; i++)
+ free(vt[i]);
+ free(vt), free(returnColumnSizes);
+ treenode_free(root);
+}
diff --git a/vertical_order_bst.py b/vertical_order_bst.py
new file mode 100644
index 0000000..e8a92ab
--- /dev/null
+++ b/vertical_order_bst.py
@@ -0,0 +1,56 @@
+# 987. Vertical Order Traversal of a Binary Tree
+from collections import defaultdict
+
+"""
+given the 'root' of a binary tree, calcuate the vertical order traversal of
+the binary tree. for each node at position '(row, col)', its left and right
+children will be at positions '(row + 1, col - 1)' and '(row + 1, col + 1)'
+respectively. the root of the tree is at '(0, 0)'. the vertical order
+traversal of a binary tree is a list of top to bottom ordering for each
+column index starting from the leftmost column and ending on the rightmost
+column. there may be multiple nodes in the same row and same column. in such
+a case, sort these nodes by their values. return the vertical order traversal
+of the binary tree
+"""
+
+
+# Definition for a binary tree node.
+class TreeNode(object):
+ def __init__(self, val=0, left=None, right=None):
+ self.val = val
+ self.left = left
+ self.right = right
+
+
+class Solution(object):
+ def helper(self, placement, level, root, _dict, limits):
+ if not root:
+ return
+ _dict[placement].append((level, root.val))
+ limits[0] = min(limits[0], placement)
+ limits[1] = max(limits[1], placement)
+ self.helper(placement - 1, level + 1, root.left, _dict, limits)
+ self.helper(placement + 1, level + 1, root.right, _dict, limits)
+
+ def verticalTraversal(self, root):
+ """
+ :type root: Optional[TreeNode]
+ :rtype: List[List[int]]
+ """
+ _dict = defaultdict(list)
+ limits = [float("inf"), float("-inf")]
+ self.helper(0, 0, root, _dict, limits)
+ ans = []
+ for i in range(limits[0], limits[1] + 1):
+ tmp = []
+ for j in sorted(_dict[i]):
+ tmp.append(j[1])
+ ans.append(tmp)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.verticalTraversal(root=[3, 9, 20, None, None, 15, 7]))
+ print(obj.verticalTraversal(root=[1, 2, 3, 4, 5, 6, 7]))
+ print(obj.verticalTraversal(root=[1, 2, 3, 4, 6, 5, 7]))