102. 二叉树的层序遍历¶
难度：中等
题目¶
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
题解¶
基本思路： 第一层只有一个元素，即根节点的值，再层序遍历左子树和右子树，合并同层的结果。
代码如下：
/**
* 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().
*/
#define MAX(x, y) (x > y ? x : y)
int *merge(int *leftBranch, int leftSize, int *rightBranch, int rightSize, int *returnSize)
{
*returnSize = leftSize + rightSize;
int *ret = (int *)malloc(sizeof(int) * (leftSize + rightSize));
if (leftSize != 0)
{
memcpy(ret, leftBranch, sizeof(int) * leftSize);
free(leftBranch);
}
if (rightSize != 0)
{
memcpy(ret + leftSize, rightBranch, sizeof(int) * rightSize);
free(rightBranch);
}
return ret;
}
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
if (root == NULL)
{
*returnSize = 0;
*returnColumnSizes = NULL;
return NULL;
}
int leftBranchSize = 0, *leftColumnSizes = NULL, **leftBranch = levelOrder(root->left, &leftBranchSize, &leftColumnSizes),
rightBranchSize = 0, *rightColumnSizes = NULL, **rightBranch = levelOrder(root->right, &rightBranchSize, &rightColumnSizes);
*returnSize = 1 + MAX(leftBranchSize, rightBranchSize);
int **ret = (int **)malloc(sizeof(int *) * *returnSize), *returnCols = (int *)malloc(sizeof(int) * *returnSize), i = 0;
*returnColumnSizes = returnCols;
*returnCols = 1;
*ret = malloc(sizeof(int));
**ret = root->val;
for (i = 1; i < *returnSize; i++)
{
if (i <= leftBranchSize && i <= rightBranchSize)
ret[i] = merge(leftBranch[i - 1], leftColumnSizes[i - 1], rightBranch[i - 1], rightColumnSizes[i - 1], returnCols + i);
else if (i <= leftBranchSize)
ret[i] = merge(leftBranch[i-1], leftColumnSizes[i-1], NULL, 0, returnCols + i);
else if (i <= rightBranchSize)
ret[i] = merge(NULL, 0, rightBranch[i-1], rightColumnSizes[i-1], returnCols + i);
}
free(leftBranch);
free(rightBranch);
free(leftColumnSizes);
free(rightColumnSizes);
return ret;
}