题解 | 二叉树的前序遍历

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
#include <stdlib.h>

int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    //将head指向root，使用head便于计算
    struct TreeNode *head = root;
    //申请一个保存这个二叉树所有节点的二维数组
    struct TreeNode **stk = malloc(sizeof(struct TreeNode) * 101);
    //用来保存返回的结果，一般使用ans或者res
    int *ans = malloc(sizeof(int) * 101);
    //用于保存存储二叉树节点的栈顶
    int top = 0;

    //设置二叉树节点返回个数为0，后面根据遍历结果实时更新该值
    *returnSize = 0;

    //如果head不为空，或者栈不为空就继续做二叉树的遍历工作
    while (head != NULL || top > 0) {
        //判断head是否为空，如果不为空就继续向二叉树的左侧遍历
        while (head != NULL) {
            //将父节点的值保存到ans里面
            ans[(*returnSize)++] = head->val;
            //将当前父节点保存到栈中，同时更新top计数
            stk[top++] = head;
            //将head指向其左子树节点
            head = head->left;
        }

        //从栈中将二叉树节点取出。
        head = stk[--top];
        //遍历右子树
        head = head->right;
    }

    return ans;
}