diff options
author | jack <0x6A73@pm.me> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <0x6A73@pm.me> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /max_width_binary_tree.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'max_width_binary_tree.c')
-rw-r--r-- | max_width_binary_tree.c | 104 |
1 files changed, 104 insertions, 0 deletions
diff --git a/max_width_binary_tree.c b/max_width_binary_tree.c new file mode 100644 index 0000000..0853205 --- /dev/null +++ b/max_width_binary_tree.c @@ -0,0 +1,104 @@ +// 662. Maximum Width of Binary Tree +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/* + * given 'root' of binary tree, return the maximum width of the + * given tree. the maximum width of a tree is the maximum width + * among all levels. the width of one level is defined as the + * length between the end-nodes (the leftmost and rightmost non + * null nodes), where the null nodes between the end-nodes that + * would be present in a complete binary tree extending down to + * that level are also counted into the length calculation. + */ + +struct TreeNode { + int val; + struct TreeNode *left; + struct TreeNode *right; +}; + +typedef enum { + QUEUELINK_OK, + QUEUELINK_EMPTY, + QUEUELINK_FULL, + QUEUELINK_ERROR = 0xFF +} queue_link; + +#define QUEUELINK_DEFINE(type) \ + typedef struct _queuelink_node_##type##_t { \ + struct _queuelink_node_##type##_t *next; \ + type value; \ + } queuelink_node_##type##_t; \ + typedef struct _queuelink_struct##type##_t { \ + queuelink_node_##type##_t *head; \ + queuelink_node_##type##_t *tail; \ + int count; \ + } queuelink_##type##_t; \ + queuelink_er_em offer_queuelink_##type(queuelink_##type##_t *queuelink, \ + type *tdata) { \ + if (tdata == NULL) \ + return QUEUELINK_ERROR; \ + queuelink_node_##type##_t *node = (queuelink_node_##type##_t *)malloc( \ + sizeof(queuelink_node_##type##_t)); \ + node->next = NULL; \ + memcpy(&node->value, tdata, sizeof(type)); \ + if (queuelink->head == NULL) { \ + queuelink->head = node; \ + queuelink->tail = node; \ + } else { \ + queuelink->tail->next = node; \ + queuelink->tail = node; \ + } \ + queuelink->count++; \ + return QUEUELINK_OK; \ + } \ + queuelink_er_em poll_queuelink_##type(queuelink_##type##_t *queuelink, \ + type *rdata) { \ + if (queuelink->head == NULL) \ + return QUEUELINK_EMPTY; \ + memcpy(rdata, &queuelink->head->value, sizeof(type)); \ + queuelink_node_##type##_t *tmp = queuelink->head; \ + queuelink->head = queuelink->head->next; \ + free(tmp); \ + queuelink->count--; \ + return QUEUELINK_OK; \ + } \ + inline int get_queuelink_size_##type(queuelink_##type##_t *queuelink_) { \ + return queuelink_->count; \ + } + +typedef struct TreeNode node_data; +QUEUELINK_DEFINE(node_data); + +int widthOfBinaryTree(struct TreeNode *root) { + queuelink_node_data_t q = {.head = NULL, .tail = NULL, .count = 0}; + offer_queuelink_node_data(&q, root); + long left = 0, right = 0; + node_data tmp; + int ans = 0; + while (1) { + int counts = get_queuelink_size_node_data(&q); + if (!counts) + break; + for (int i = 0; i < counts; i++) { + poll_queuelink_node_data(&q, &tmp); + if (!i) + left = tmp.val; + right = tmp.val; + if (tmp.left != NULL) { + tmp.left->val = tmp.val * 2L; + offer_queuelink_node_data(&q, tmp.left); + } + if (tmp.right != NULL) { + tmp.right->val = tmp.val * 2L + 1; + offer_queuelink_node_data(&q, tmp.right); + } + int tmp_ans = right - left + 1; + if (ans < tmp_ans) + ans = tmp_ans; + } + } + return ans; +} |