牛客网——实现二叉树先序、中序和后序遍历

title: 牛客网——实现二叉树先序、中序和后序遍历

题目描述：

分别按照二叉树先序，中序和后序打印所有的节点。

示例：

输入：

{1,2,3}

返回值：

[[1,2,3],[2,1,3],[2,3,1]]

备注：
$$
n \leqslant 10^6
$$
代码如下：

(照着别人的代码敲的，待重新实现一遍)

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

/*前序遍历实现节点计数器，计算了以当前节点为根节点的子树的节点总数*/
void get_nodeNum(struct TreeNode* root, int* count)
{
    ++(*count);
    if(root->left){
        get_nodeNum(root->left, count);
    }
    if(root->right){
        get_nodeNum(root->right, count);
    }    
}

/*前序遍历*/
void pre_order_traversal(struct TreeNode* root, int* nodes, int* count)
{
    nodes[(*count)++] = root->val;
    if(root->left){
        pre_order_traversal(root->left, nodes, count);
    }
    if(root->right){
        pre_order_traversal(root->right, nodes, count);
    }
}

/*中序遍历*/
void in_order_traversal(struct TreeNode* root, int* nodes, int* count)
{
    if(root->left){
        in_order_traversal(root->left, nodes, count);
    }
    nodes[(*count)++] = root->val;
    if(root->right){
        in_order_traversal(root->right, nodes, count);
    }
}

/*后续遍历*/
void post_order_traversal(struct TreeNode* root, int* nodes, int* count)
{
    if(root->left){
        post_order_traversal(root->left, nodes, count);
    }
    if(root->right){
        post_order_traversal(root->right, nodes, count);
    }
    nodes[(*count)++] = root->val;
}

/**
 * 
 * @param root TreeNode类 the root of binary tree
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
int** threeOrders(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {
    // write code here
    int **pp_result = NULL;
    if(root){
        int tree_size = 0;
        get_nodeNum(root, &tree_size);
        if(tree_size){
            int index = 0;
            *returnSize = 3;
            pp_result = (int**)malloc(sizeof(int*) * 3);
            int *pre_order_result = (int*)malloc(sizeof(int) * tree_size);
            pre_order_traversal(root, pre_order_result, &index);
            pp_result[0] = pre_order_result;
            
            index = 0;
            
            int* in_order_result = (int*)malloc(sizeof(int) * tree_size);
            in_order_traversal(root, in_order_result, &index);
            pp_result[1] = in_order_result;
            
            index = 0;
            
            int* post_order_result = (int*)malloc(sizeof(int) * tree_size);
            post_order_traversal(root, post_order_result, &index);
            pp_result[2] = post_order_result;
            
            int *columns = (int*)malloc(sizeof(int)*3);
            columns[0] = columns[1] = columns[2] = tree_size;
            *returnColumnSizes = columns;
        }
    }
    return pp_result;
}

运行结果：

运行时间：3ms

占用内存：364k