leetcode刷题日记:94. Binary Tree Inorder Traversal(二叉树的中序遍历)

94. Binary Tree Inorder Traversal(二叉树的中序遍历)

给出二叉树的根结点，返回二叉树的中序遍历序列。
二叉树的中序遍历序列是先遍历左子树再遍历根结点然后再遍历右子树，在遍历左子树是这个结点是左子树的根结点，左子树有左子树和根结点右子树，也就是说在遍历的时候我们要递归遍历。
在递归遍历中我们需要不断的进行分配空间与释放空间，然后我们在这个过程中不断的进行序列的合并，在合并的过程中需要我们注意的是合并的顺序是左子树、根结点、右子树，同时在合并之后要将合并后的returnSize计算出来。
在这一个二叉树的中序遍历中有一点那个归并排序的感觉，将问题分解成小问题后得到答案然后再答案合并，非常像，不知道大家有没有这一种感觉。

int * inorderTraversal(struct TreeNode * root, int *returnSize){
    if(root!=NULL){
        int *left = inorderTraversal(root->left, returnSize);
        int leftLength = *returnSize; 
        int *right = inorderTraversal(root->right, returnSize);
        int rightLength = *returnSize;
        int num = leftLength + rightLength;
        int *answer = (int *)malloc(sizeof(int)*(num+1));
        int k = 0;
        for(int i=0; i<leftLength; i++){
            answer[k++] = left[i];
        }
        answer[k++] = root->val;
        for(int i=0; i<rightLength; i++){
            answer[k++] = right[i];
        }
        free(left);
        free(right);
        left = NULL;
        right = NULL;
        *returnSize = num+1;
        return answer;
    }
    *returnSize = 0;
    return NULL;
}
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

运行结果截图：

145. Binary Tree Postorder Traversal(后序遍历)

二叉树的前序后序中序遍历都非常类似，只是对于根结点的访问顺序发生改变，我们可以出如下代码:

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    if(root!=NULL){
        int *left = postorderTraversal(root->left, returnSize);
        int leftLength = *returnSize; 
        int *right = postorderTraversal(root->right, returnSize);
        int rightLength = *returnSize;
        int num = leftLength + rightLength;
        int *answer = (int *)malloc(sizeof(int)*(num+1));
        int k = 0;
        for(int i=0; i<leftLength; i++){
            answer[k++] = left[i];
        }
        for(int i=0; i<rightLength; i++){
            answer[k++] = right[i];
        }
        answer[k++] = root->val;
        free(left);
        free(right);
        left = NULL;
        right = NULL;
        *returnSize = num+1;
        return answer;
    }
    *returnSize = 0;
    return NULL;
}
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

运行结果截图: