aboutsummaryrefslogtreecommitdiff
path: root/max_width_binary_tree.c
blob: 0853205497d6ace622bfc544dcff33106735f2ae (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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;
}