LeetCode 0094 0144

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;
    
17. 
    
18. void stk_init(STK *s)
    
19. {
    
20.     s->top=0;
21. }
    
22. 
    
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. }
    
32. 
    
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. }
    
33. 
    
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. }
    
42. 
    
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;
    
52. 
    
53.     stk_init(s);
    
54. 
    
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. }
    
33. 
    
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. }
    
42. 
    
43. int stk_empty(STK* s){
    
44.     return s->top;
    
45. }
    
46. 
    
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. }

迭代代码结束