问题描述

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

求解思路

递归：
在外层接口函数preorderTraversal()中申请空间并传递给核心的preorder()函数，在其中前序递归访问二叉树上的每一个节点。

使用栈迭代：

//外层大循环：
while(非空节点||栈非空){
	//内层小循环
	while(非空节点){
		访问该节点；
		该节点入栈；
		指向左儿子；
	}
	出栈一个节点；
	指向右儿子；
}

代码实现

递归实现：

void preorder(struct TreeNode* root, int* resultArray, int* returnSize) {
    if (root == NULL)
        return;
    resultArray[(*returnSize)++] = root->val;
    preorder(root->left, resultArray, returnSize);
    preorder(root->right, resultArray, returnSize);
    return;
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* resutlArray = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    preorder(root, resutlArray, returnSize);
    return resutlArray;
}

使用栈迭代实现：

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* resutlArray = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    struct TreeNode* stk[100];
    int top = 0;
    while (root != NULL || top > 0) {
        while (root != NULL) {
            //前序遍历
            resutlArray[(*returnSize)++] = root->val;
            stk[top++] = root;
            root = root->left;
        }
        root = stk[--top];
        root = root->right;
    }

    return resutlArray;
}

收获和疑惑

注意C语言中多层递归函数共享同一个变量的方式：传递指针。
还有一种S(1)的Morris中序遍历算法，看不懂。