2016年2月5日 星期五

LEET code -- Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3


return [1,2,3].

反正就是走前序
root, left, right
中序
left,root,right
後續
left,right,root

但是因為不知道有多少資料要被記錄
所以要先知道tree的深度，才知道要先malloc多少記憶體空間
再把資料刷進去

要注意returnSize 這邊是指標  但是他外面應該是(&returnSize)傳進來的
所以直接給他值就好




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int Height = findHeight(root);
    int Size=0;
    int *travel =(int *)malloc(sizeof(int)*pow(2,Height));
    travelorder(root,&Size,travel);
    *returnSize=Size;
    printf("ans:%d,size=%d ",travel[0],*returnSize);
    return travel;
}

int travelorder(struct TreeNode* root, int *Size,int *travel){
    if(root==NULL)return;
    travel[*Size]=root->val;
    printf("size=%d ,value=%d ",*Size,root->val);
    *Size+=1;
    travelorder(root->left,Size,travel);
    
    travelorder(root->right,Size,travel);
    return;
    
}

int findHeight(struct TreeNode* root){
    if(root==NULL)return 0 ;
    int l=findHeight(root->left);
    int r=findHeight(root->right);
    return 1+ (l>=r? l:r);
}
-----

iterative 

必須要寫一個stack來控制


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    //int Height = findHeight(root);
    int StackSize=0,TravelSize=0,StackCap=128,TravelCap=128;
    struct TreeNode ** stack=malloc(sizeof(struct TreeNode*)*StackCap);
    int *travel =(int *)malloc(sizeof(int)*TravelCap);
    stack[StackSize++]=root;
    while(StackSize!=0){
        struct TreeNode *temp = stack[--StackSize];
        if (temp!=NULL){
            if(StackSize >=StackCap*0.75 ){
                //increase stack size
                stack=realloc(stack,sizeof(struct TreeNode*)*StackCap*2);
                StackCap*=2;
            }
            if(TravelSize >= TravelCap*0.75){
                travel = realloc(travel,sizeof(int)*TravelCap*2);
                TravelCap*=2;
            }
            travel[TravelSize++]=temp->val;
            stack[StackSize++]=temp->right;//because the left need to be out first
            stack[StackSize++]=temp->left;
            
        }
    }
    *returnSize=TravelSize;
    printf("ans:%d,size=%d ",travel[0],*returnSize);
    return travel;
}
張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)