LeetCode 0094 0144

4580阅读　0评论2019-01-01　zhln
分类：BSD

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. }
迭代代码结束














上一篇：LeetCode 0100 0101
下一篇：LeetCode 108