【二叉树】前序遍历迭代实现

做题思路：用栈迭代解决

1.用一个数组模拟栈。先将根结点入栈，然后设置一个int值stack_top指向栈顶

2.当栈中有元素时，先将栈中元素出栈。放入到要返回数组中

3.然后将此元素右孩子（若不为NULL）先压入栈，再将左孩子（若不为NULL）入栈

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int* ret = (int*)malloc(sizeof(int) * 100);
    struct TreeNode* stack[100] = { 0 };
    if(root == NULL)
        return ret;
    int stack_top = 0;
    stack[stack_top++] = root;
    struct TreeNode* temp;

    while(stack_top) {
        temp = stack[--stack_top];
        ret[(*returnSize)++] = temp->val;
        if(temp->right) 
            stack[stack_top++] = temp->right;
        if(temp->left)
            stack[stack_top++] = temp->left;
    }

    return ret;
}

做题思路：用栈迭代解决

做题思路：用栈迭代中序遍历

1.先判断给定结点是否为NULL，若是，直接返回

2.创建一个TreeNode*数组模拟栈。创建一个int值stack_top追踪栈顶元素

3.先将根结点入栈，然后入栈其左孩子，再入栈左孩子的左孩子

4.当栈中结点无左孩子时，出栈栈顶元素，放入数组中。再查看其右孩子，依次类推

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int* ret = (int*)malloc(sizeof(int) * 100);

    if(!root)
        return ret;

    struct TreeNode* stack[100];
    int stack_top = 0;

    struct TreeNode* cur = root;
    
    //当cur存在或者栈中有元素（有时候栈中没有元素，但是cur还存储着右子树）时进行循环
    while(cur || stack_top) {
        //指针访问到底层结点
        if(cur != NULL) {
            stack[stack_top++] = cur;
            cur = cur->left;
        } 
        //这时左子树遍历完成，将栈顶元素拿出遍历根结点和右子树
        else {
            cur = stack[--stack_top];
            ret[(*returnSize)++] = cur->val;
            cur = cur->right;
        }
    }
    return ret;
}

做题思路：用栈迭代解决

后序遍历其实就是将二叉树先前序遍历生成数组（但是生成的数组要是中右左，这样反转后才是左右中），然后再反转

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int* ret = (int*)malloc(sizeof(int) * 100);
    struct TreeNode* stack[100] = { 0 };
    if(root == NULL)
        return ret;
    int stack_top = 0;
    stack[stack_top++] = root;
    struct TreeNode* temp;

    while(stack_top) {
        temp = stack[--stack_top];
        ret[(*returnSize)++] = temp->val;
        if(temp->left) 
            stack[stack_top++] = temp->left;
        if(temp->right)
            stack[stack_top++] = temp->right;
    }

    int i = 0;
    for(i = 0; i < *returnSize/2; i++) {
        ret[i] ^= ret[*returnSize - i-1];
        ret[*returnSize - i-1] ^= ret[i];
        ret[i] ^= ret[*returnSize - i-1];
    }

    return ret;
}