二叉树的前序/中序/后序遍历—采用递归与迭代两种方法实现（以leetcode二叉树遍历为例题）
前序遍历
递归算法
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int* preorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = 0; int * returns = (int *)malloc(sizeof(int)* 110); preorder(root,returns,returnSize); return returns; } void preorder(struct TreeNode* root,int returns[],int *returnSize) { if(root == NULL) { return; } // printf("%d",root->val); // preorder(root,returns,&returnSize); returns[*returnSize] = root->val; (*returnSize)++; preorder(root->left,returns,returnSize); preorder(root->right,returns,returnSize); }
迭代
这里比较详细🔎（复杂）的写出来，包括栈的存储方式定义，入栈，出栈，判空以及初始化方法，下面中序与后序遍历时进行了优化！减少了多个方法函数！
::重点记忆后边的写法::
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ typedef struct stack{ struct TreeNode* data[110]; int top; }stack; void push(stack *s,struct TreeNode *x) { s->data[(s->top)] = x; (s->top)++; } struct TreeNode *pop(stack *s,struct TreeNode *x) { x = s->data[--(s->top)]; // printf("%d",x->val); return x; } void init(stack *s) { (s->top) = 0; } int empty(stack s) { if(s.top == 0) return 0; return 1; } void visit(struct TreeNode* x,int returns[],int *returnSize) { returns[(*returnSize)++] = x->val; } int* preorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = 0; int* returns = (int *)malloc(sizeof(int)* 110); struct TreeNode *m; m = root; stack s; init(&s); while(m != NULL || empty(s)!= 0) { if(m) { visit(m,returns,returnSize); push(&s,m); // printf("s%ds",m->val); m = m->left; } else { m = pop(&s,m); m = m->right; } } return returns; }
中序遍历
递归算法
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int* inorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = 0; int *returns = (int *)malloc(sizeof(int )* 110); inorder(root,returns,returnSize); return returns; } void inorder(struct TreeNode* root,int returns[],int *returnSize) { if(root == NULL) return; inorder(root->left,returns,returnSize); returns[(*returnSize)++] = root->val; inorder(root->right,returns,returnSize); }
迭代
我们也可以用迭代的方式实现递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，代码附下。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int* inorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = 0; int* returns = (int *)malloc(sizeof(int )*110); struct TreeNode *s[110]; int top = 0; struct TreeNode *m = root; while(m!=NULL || top != 0) { if(m) { s[top++] = m; m = m->left; } else { m = s[--top]; returns[(*returnSize)++] = m->val; m = m -> right; } } return returns; }
后序遍历
递归
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int* postorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = 0; int *returns = (int *)malloc(sizeof(int)* 110); postorder(root,returns,returnSize); return returns; } void postorder(struct TreeNode* root,int returns[],int *returnSize) { if(root == NULL) { return; } postorder(root->left,returns,returnSize); postorder(root->right,returns,returnSize); returns[(*returnSize)++] = root->val; }
迭代 （卡了一会儿）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int* postorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = 0; int *returns = (int *)malloc(sizeof(int)* 110); struct TreeNode* data[110]; int top = 0; struct TreeNode* m = root; struct TreeNode* pre = NULL; while(m || top != 0) { while(m) { pre = m; data[top++] = m; m = m->left; } m = data[--top]; //当前m为空，肯定要m找到上一个结点，才能判断 if(m->right != NULL && m->right != pre) //下面还有子结点 { data[top++] = m; m = m->right; } else { pre = m; //pre记录现在的结点 当m->right与pre相等时可以记录当前结点 returns[(*returnSize)++] = pre->val; m = NULL; //m去栈里找栈顶元素 } } return returns; }
