Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
按層次順序遍歷二叉樹，輸出二維數(shù)組
還是使用遞歸即可，由于測試數(shù)據(jù)二叉樹高度比較大，二維數(shù)組申請內(nèi)存時需要多申請些。
/**
* 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 *columnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
void level(struct TreeNode* root, int** columnSizes, int* returnSize,int** ans,int height)
{
if(height>*returnSize)
{
*returnSize=*returnSize+1;
ans[height-1]=(int *)malloc(sizeof(int)*100000);
(*columnSizes)[height-1]=0;
}
if(root==NULL)return;
ans[height-1][(*columnSizes)[height-1]]=root->val;
//printf("%d: %d %d\n",height-1,(*columnSizes)[height-1],ans[height-1][(*columnSizes)[height-1]]);
(*columnSizes)[height-1]=(*columnSizes)[height-1]+1;
if(root->left!=NULL)
level(root->left,columnSizes,returnSize,ans,height+1);
if(root->right!=NULL)
level(root->right,columnSizes,returnSize,ans,height+1);
return;
}
int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
int **ans=(int**)malloc(sizeof(int*)*1000);
*returnSize=0;
*columnSizes=(int *)malloc(sizeof(int)*1000);
if(root==NULL)return ans;
level(root,columnSizes,returnSize,ans,1);
return ans;
}
