注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex103 Binary Tree Zigzag Level Order Traversal  

2015-05-19 22:49:25|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这个题目是从ex102变过来

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]
当时做这个时候没有用队列来保存数据,直接用的input  ouput输出来迭代输出每层,然后result数组保存结果。
所以做这个的时候就比较简单了,偶数层直接reverse一下就行了。当然,按照标准的做法也可以用队列,然后在偶数层倒序遍历,貌似这个时候就不能直接用队列了。我的实现代码

int traverse(struct TreeNode** current, int nums, struct TreeNode** output)
{
//这个函数是用来获取下一层不是NULL的节点
//并返回下层非NULL的个数
int i = 0;
int len = 0;
for (i = 0; i < nums; i++)
{
if (current[i]->left != NULL)
{
output[len] = current[i]->left;
len++;
}
if (current[i]->right != NULL)
{
output[len] = current[i]->right;
len++;
}
}
return len;
}

int reverse(int *nums, int numSize)
{
int*temp = (int*)malloc(numSize*sizeof(int));
int i = 0, j = numSize - 1;
while (i < numSize)
{
temp[i] = nums[j];
i++;
j--;
}
memcpy(nums, temp, numSize*sizeof(int));
free(temp);
temp = NULL;
return 0;

}
int** zigzagLevelOrder(struct TreeNode* root, int** columnSizes, int* returnSize){
if (root == NULL)
return NULL;
struct TreeNode* input[4000], *output[4000];
int height = 1000;
int nums = 1;
int width = 4000;
int i;
columnSizes[0] = (int*)malloc(height*sizeof(int));
int **result = (int**)malloc(height* sizeof(int*));

for (i = 0; i < width; i++)
{
input[i] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
output[i] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
}
int len = 0;

result[len] = (int*)malloc(nums*sizeof(int));
result[len][0] = root->val; //这是root层
columnSizes[0][0] = nums;

nums = traverse(&root, nums, output);
memcpy(input, output, nums*sizeof(struct TreeNode*));
//获取到下层之后,复制到input里面去
len++;
result[len] = (int*)malloc(nums*sizeof(int));
while (nums >= 1)
{

for (i = 0; i < nums; i++)
{
result[len][i] = output[i]->val;//复制到result里面去
}
columnSizes[0][len] = nums;

len++;
nums = traverse(input, nums, output);
result[len] = (int*)malloc(nums*sizeof(int));//动态分配空间
memcpy(input, output, nums*sizeof(struct TreeNode*));
//获取到下层之后,复制到input里面去
}
returnSize[0] = len;
for (i = 0; i < len; i ++)
{
if (i % 2 == 0)
{
//left ->right
}
else
{
//right->left
reverse(result[i], columnSizes[0][i]);
}
}

return result;
}







  评论这张
 
阅读(14)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017