diff options
-rw-r--r-- | misc.cpp | 20 | ||||
-rw-r--r-- | vertical_order_bst.c | 103 | ||||
-rw-r--r-- | vertical_order_bst.py | 56 |
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])) |