-
Notifications
You must be signed in to change notification settings - Fork 0
/
102.二叉树的层序遍历.c
91 lines (85 loc) · 2.22 KB
/
102.二叉树的层序遍历.c
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
/*
* @lc app=leetcode.cn id=102 lang=c
*
* [102] 二叉树的层序遍历
*
* https://leetcode-cn.com/problems/binary-tree-level-order-traversal/description/
*
* algorithms
* Medium (63.17%)
* Likes: 600
* Dislikes: 0
* Total Accepted: 179.1K
* Total Submissions: 283.5K
* Testcase Example: '[3,9,20,null,null,15,7]'
*
* 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
*
*
*
* 示例:
* 二叉树:[3,9,20,null,null,15,7],
*
* 3
* / \
* 9 20
* / \
* 15 7
*
*
* 返回其层次遍历结果:
*
* [
* [3],
* [9,20],
* [15,7]
* ]
*
*
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
void bfs(struct TreeNode* root, int* returnSize, int* returnColumnSizes, int **retVal){
struct TreeNode* queue[10000] = {0};
int front, back;
struct TreeNode* cur;
front = back = 0;
queue[back++] = root;
while (front < back) {
int cnt = back - front;
returnColumnSizes[*returnSize] = cnt;
retVal[*returnSize] = malloc(sizeof(int) * 10240);
for (int i = 0; i < cnt; i++) {
cur = queue[front++];
retVal[*returnSize][i] = cur->val;
if (cur->left)
queue[back++] = cur->left;
if (cur->right)
queue[back++] = cur->right;
}
(*returnSize)++;
}
return;
}
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
int **retVal = (int *)malloc(sizeof(int) * 10240);
*returnColumnSizes = (int *)malloc(sizeof(int) * 10240);
*returnSize = 0;
if (root == NULL)
return NULL;
bfs(root, returnSize, *returnColumnSizes, retVal);
return retVal;
}
// @lc code=end