Chinaunix首页 | 论坛 | 博客

熟睡的企鹅finekill.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

zhln

  • 博客访问： 1545068
  • 博文数量： 327
  • 博客积分： 10000
  • 博客等级： 上将
  • 技术积分： 3556
  • 用 户 组： 普通用户
  • 注册时间： 2005-04-05 21:28
个人简介

东黑布衣，流浪幽燕。 真诚善良，值得信赖。

文章分类

全部博文（327）

我的朋友
推荐博文
相关博文
LeetCode 0094 0144

分类： BSD

2019-01-01 23:07:23

94. Binary Tree Inorder Traversal
Medium

Given a binary tree, return the inorder traversal of its nodes' values.

Example: 

Input: [1,null,2,3]
   1
    \
     2
    /
   3 Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?


  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  * int val;
  5.  * struct TreeNode *left;
  6.  * struct TreeNode *right;
  7.  * };
  8.  */
  9. /**
  10.  * Return an array of size *returnSize.
  11.  * Note: The returned array must be malloced, assume caller calls free().
  12.  */
  13. typedef struct stk{
  14.    int top;
  15.    int *nd;
  16. }STK;

  18. void stk_init(STK *s)
  19. {
  20.     s->top=0;
  21. }

  23. void stk_push(STK *s,int val)
  24. {
  25.     if(s->top==0)
  26.         s->nd = (int*)malloc(sizeof(int));
  27.     else
  28.         s->nd = (int*)realloc(s->nd,sizeof(int)*(s->top+1));
  29.     s->nd[s->top]=val;
  30.     s->top+=1;
  31. }

  33. void inorder(struct TreeNode* root, STK* stack){
  34.     if(root==NULL)
  35.         return;
  36.     inorder(root->left,stack);
  37.     stk_push(stack,root->val);
  38.     inorder(root->right,stack);
  39. }
  40. int* inorderTraversal(struct TreeNode* root, int* returnSize) {
  41.     STK* stack=(STK*)malloc(sizeof(STK));
  42.     stk_init(stack);
  43.     inorder(root,stack);
  44.     *returnSize=stack->top;
  45.     return stack->nd;
  46. }

迭代算法1
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  * int val;
  5.  * struct TreeNode *left;
  6.  * struct TreeNode *right;
  7.  * };
  8.  */
  9. /**
  10.  * Return an array of size *returnSize.
  11.  * Note: The returned array must be malloced, assume caller calls free().
  12.  */
  13. typedef struct stk{
  14.     int top;
  15.     struct TreeNode *nd;
  16. }STK;
  17. void stk_init(STK* s){
  18.     s->top=0;
  19.     s->nd=NULL;
  20. }
  21. void stk_push(STK* s, struct TreeNode* nd){
  22.     if(nd==NULL)
  23.         return;
  24.     if(s->nd==NULL)
  25.         s->nd = (struct TreeNode*)malloc(sizeof(struct TreeNode));
  26.     else
  27.         s->nd = (struct TreeNode*)realloc(s->nd, sizeof(struct TreeNode)*(s->top+1));
  28.     s->nd[s->top].val = nd->val;
  29.     s->nd[s->top].left = nd->left;
  30.     s->nd[s->top].right = nd->right;
  31.     s->top+=1;
  32. }

  34. struct TreeNode* stk_pop(STK* s){
  35.     if(s->top<1)
  36.         return NULL;
  37.     struct TreeNode* r;
  38.     s->top-=1;
  39.     r = &(s->nd[s->top]);
  40.     return r;
  41. }

  43. int stk_empty(STK* s){
  44.     return s->top;
  45. }
  46. int* inorderTraversal(struct TreeNode* root, int* returnSize) {
  47.     int* result=NULL;
  48.     int index=0;
  49.     STK* s = (STK*)malloc(sizeof(STK));
  50.     if(root==NULL)
  51.        return NULL;

  53.     stk_init(s);

  55.     while(stk_empty(s)!=0 || root!=NULL){
  56.         while(root!=NULL){
  57.             stk_push(s,root);
  58.             root=root->left;
  59.         }
  60.         if(stk_empty(s)!=0){
  61.             root=stk_pop(s);
  62.             if(root!=NULL){
  63.                 if(result==NULL){
  64.                     result = (int*)malloc(sizeof(int));
  65.                     result[index] = root->val;
  66.                 }else{
  67.                     result = (int*)realloc(result, sizeof(int)*(index+1));
  68.                     result[index] = root->val;
  69.                 }
  70.                 index+=1;
  71.                 root=root->right;
  72.             }
  73.         }
  74.     }
  75.     *returnSize=index;
  76.     return result;
  77. }
迭代算法1



144. Binary Tree Preorder Traversal
Medium

Given a binary tree, return the preorder traversal of its nodes' values.

Example: 

Input: [1,null,2,3] 1
    \
     2
    /
   3 Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

递归代码开始
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  * int val;
  5.  * struct TreeNode *left;
  6.  * struct TreeNode *right;
  7.  * };
  8.  */
  9. /**
  10.  * Return an array of size *returnSize.
  11.  * Note: The returned array must be malloced, assume caller calls free().
  12.  */
  13. typedef struct stk{
  14.     int top;
  15.     int *nd;
  16. }STK;
  17. void stk_init(STK* s){
  18.     s->top=0;
  19. }
  20. void stk_push(STK* s, int val){
  21.     if(s->top==0)
  22.         s->nd = (int*)malloc(sizeof(int));
  23.     else
  24.         s->nd = (int*)realloc(s->nd, sizeof(int)*(s->top+1));
  25.     s->nd[s->top] = val;
  26.     s->top+=1;
  27. }
  28. void preorder(struct TreeNode* r, STK* s){
  29.     if(r==NULL)
  30.         return;
  31.     stk_push(s, r->val);
  32.     preorder(r->left, s);
  33.     preorder(r->right, s);
  34. }
  35. int* preorderTraversal(struct TreeNode* root, int* returnSize) {
  36.     STK* s = (STK*)malloc(sizeof(STK));
  37.     stk_init(s);
  38.     preorder(root, s);
  39.     *returnSize = s->top;
  40.     return s->nd;
  41. }
递归代码结束


迭代代码开始
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  * int val;
  5.  * struct TreeNode *left;
  6.  * struct TreeNode *right;
  7.  * };
  8.  */
  9. /**
  10.  * Return an array of size *returnSize.
  11.  * Note: The returned array must be malloced, assume caller calls free().
  12.  */
  13. typedef struct stk{
  14.     int top;
  15.     struct TreeNode *nd;
  16. }STK;
  17. void stk_init(STK* s){
  18.     s->top=0;
  19.     s->nd=NULL;
  20. }
  21. void stk_push(STK* s, struct TreeNode* nd){
  22.     if(nd==NULL)
  23.         return;
  24.     if(s->nd==NULL)
  25.         s->nd = (struct TreeNode*)malloc(sizeof(struct TreeNode));
  26.     else
  27.         s->nd = (struct TreeNode*)realloc(s->nd, sizeof(struct TreeNode)*(s->top+1));
  28.     s->nd[s->top].val = nd->val;
  29.     s->nd[s->top].left = nd->left;
  30.     s->nd[s->top].right = nd->right;
  31.     s->top+=1;
  32. }

  34. struct TreeNode* stk_pop(STK* s){
  35.     if(s->top<1)
  36.         return NULL;
  37.     struct TreeNode* r;
  38.     s->top-=1;
  39.     r = &(s->nd[s->top]);
  40.     return r;
  41. }

  43. int stk_empty(STK* s){
  44.     return s->top;
  45. }

  47. int* preorderTraversal(struct TreeNode* root, int* returnSize) {
  48.     struct TreeNode* t;
  49.     struct TreeNode* left;
  50.     struct TreeNode* right;
  51.     int* result=NULL;
  52.     int index=0;
  53.     STK* s = (STK*)malloc(sizeof(STK));
  54.     if(root==NULL)
  55.         return NULL;
  56.     stk_init(s);
  57.     stk_push(s, root);
  58.     while(stk_empty(s)!=0){
  59.         t = stk_pop(s);
  60.         if(t!=NULL){
  61.             if(result==NULL){
  62.                 result = (int*)malloc(sizeof(int));
  63.                 result[index] = t->val;
  64.             }else{
  65.                 result = (int*)realloc(result, sizeof(int)*(index+1));
  66.                 result[index] = t->val;
  67.             }
  68.             index+=1;
  69.             left=t->left;//下面push的时候,s->top会变,这里必须临时变量保存
  70.             right=t->right;
  71.             stk_push(s,right);
  72.             stk_push(s,left);
  73.         }
  74.     }
  75.     *returnSize=index;
  76.     return result;
  77. }
迭代代码结束














阅读(4510) | 评论(0) | 转发(0) |
0

上一篇：LeetCode 0100 0101

下一篇：LeetCode 108

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6