【数据结构与算法】二叉树前序，中序，后序遍历非递归版。Leetcode接口
144. 二叉树的前序遍历 - 力扣（LeetCode）
- 如果根节点为空，直接返回。
- 初始化一个辅助栈
s，并将根节点入栈。 - 重复以下步骤，直到栈为空：
- 检查当前节点
tmp：- 如果
tmp不为空：- 将当前节点
tmp入栈，并将节点值tmp->val添加到结果数组a中。 - 将当前节点的左子节点赋值给
tmp，继续进行下一轮循环。
- 将当前节点
- 如果当前节点
tmp为空：- 获取栈顶节点的右子节点赋值给
tmp。 - 弹出栈顶节点。
- 获取栈顶节点的右子节点赋值给
- 如果
- 检查当前节点
- 遍历结束后，结果数组
a中存储的就是二叉树前序遍历的结果。
typedef struct TreeNode* DataType;
typedef struct StackNode
{
DataType data;
struct StackNode* next;
}StackNode;
typedef struct Stack
{
StackNode* top;
}Stack;
void StackInit(Stack* s)
{
s->top = NULL;
}
int StackEmpty(Stack* s)
{
return s->top == NULL;
}
void StackPush(Stack* s, DataType x)
{
StackNode* tmp = (StackNode*)malloc(sizeof(StackNode));
tmp->data = x;
tmp->next = NULL;
if(s->top == NULL)
{
s->top = tmp;
}
else
{
tmp->next = s->top;
s->top = tmp;
}
}
DataType StackTop(Stack* s)
{
if(!StackEmpty(s))
{
return s->top->data;
}
return NULL;
}
void StackPop(Stack* s)
{
if(!StackEmpty(s))
{
StackNode* tmp = s->top;
s->top = s->top->next;
free(tmp);
}
else
{
exit(-1);
}
}
int TreeSize(struct TreeNode* root) {
return root == NULL ? 0 : 1 + TreeSize(root->left) + TreeSize(root->right);
}
void pre_order(struct TreeNode* root, int* a, int* i) {
if(root==NULL)
{
return;
}
Stack s;
StackInit(&s);
struct TreeNode* tmp = root;
while(tmp || !StackEmpty(&s))
{
if(tmp)
{
StackPush(&s,tmp);
a[(*i)++] = tmp -> val;
tmp = tmp -> left;
}
else
{
tmp = StackTop(&s) -> right;
StackPop(&s);
}
}
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
int n = TreeSize(root);
*returnSize = n;
int* a = (int*)malloc(sizeof(int) * n);
int i = 0;
pre_order(root, a, &i);
return a;
}94. 二叉树的中序遍历 - 力扣（LeetCode）
首先创建一个空的栈 s，再用一个临时指针 tmp 指向根节点 root。
然后进行循环，直到 tmp 指针为空且栈为空。在循环中，如果 tmp 指针不为空，则将 tmp 入栈，并将 tmp 移动到其左子树。
如果 tmp 指针为空，则表示已经到达最左边的叶子节点，此时将栈顶节点出栈，将节点的值存入数组 a 中，并将 tmp 指向该节点的右子树。
typedef struct TreeNode* DataType;
typedef struct StackNode
{
DataType data;
struct StackNode* next;
}StackNode;
typedef struct Stack
{
StackNode* top;
}Stack;
void StackInit(Stack* s)
{
s->top = NULL;
}
int StackEmpty(Stack* s)
{
return s->top == NULL;
}
void StackPush(Stack* s, DataType x)
{
StackNode* tmp = (StackNode*)malloc(sizeof(StackNode));
tmp->data = x;
tmp->next = NULL;
if(s->top == NULL)
{
s->top = tmp;
}
else
{
tmp->next = s->top;
s->top = tmp;
}
}
DataType StackTop(Stack* s)
{
if(!StackEmpty(s))
{
return s->top->data;
}
return NULL;
}
void StackPop(Stack* s)
{
if(!StackEmpty(s))
{
StackNode* tmp = s->top;
s->top = s->top->next;
free(tmp);
}
else
{
exit(-1);
}
}
void inorder(struct TreeNode* root,int **a,int *pi)
{
if(root==NULL)
{
return;
}
Stack s;
StackInit(&s);
struct TreeNode* tmp = root;
while(tmp || !StackEmpty(&s))
{
if(tmp)
{
StackPush(&s, tmp);
tmp=tmp->left;
}
else
{
tmp = StackTop(&s);
(*a)[(*pi)++] = tmp->val;
StackPop(&s);
tmp = tmp->right;
}
}
}
int treesize(struct TreeNode* root)
{
if(root==NULL)
{
return 0;
}
return 1+treesize(root->left)+treesize(root->right);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int count=treesize(root);
int *a=(int*)malloc(count*sizeof(int));
int pi=0;
inorder(root,&a,&pi);
*returnSize=pi;
return a;
}145. 二叉树的后序遍历 - 力扣（LeetCode）
具体的逻辑如下：
- 如果根节点为空，直接返回。
- 初始化一个辅助栈
stack，并将根节点入栈。 - 重复以下步骤，直到栈为空：
- 将当前节点及其左子节点依次入栈，直到当前节点的左子节点为空。
- 检查当前栈顶节点的右子节点：
- 如果右子节点为空或者已经访问过（即和
prev指向的节点相同），说明当前节点的右子树已经处理完毕，将栈顶节点弹出，并将节点值添加到结果数组中。 - 否则，继续处理右子节点，将右子节点赋值给当前节点，并进行下一轮循环。
- 如果右子节点为空或者已经访问过（即和
- 更新
prev指向当前处理的节点。
- 遍历结束后，结果数组中存储的就是二叉树后序遍历的结果。
typedef struct TreeNode* DataType;
typedef struct StackNode
{
DataType data;
struct StackNode* next;
}StackNode;
typedef struct Stack
{
StackNode* top;
}Stack;
void StackInit(Stack* s)
{
s->top = NULL;
}
int StackEmpty(Stack* s)
{
return s->top == NULL;
}
void StackPush(Stack* s, DataType x)
{
StackNode* tmp = (StackNode*)malloc(sizeof(StackNode));
tmp->data = x;
tmp->next = NULL;
if(s->top == NULL)
{
s->top = tmp;
}
else
{
tmp->next = s->top;
s->top = tmp;
}
}
DataType StackTop(Stack* s)
{
if(!StackEmpty(s))
{
return s->top->data;
}
return NULL;
}
void StackPop(Stack* s)
{
if(!StackEmpty(s))
{
StackNode* tmp = s->top;
s->top = s->top->next;
free(tmp);
}
else
{
exit(-1);
}
}
void postorder(struct TreeNode* root, int **a, int *pi) {
if (root == NULL) {
return;
}
struct TreeNode* prev = NULL;
Stack stack;
StackInit(&stack);
struct TreeNode* current = root;
while (current != NULL || !StackEmpty(&stack)) {
// 将当前节点及其左子节点依次入栈
while (current != NULL) {
StackPush(&stack, current);
current = current->left;
}
// 检查当前栈顶节点的右子节点
// 如果右子节点为空或者已经访问过，则将栈顶节点弹出并添加到结果数组中
if (StackTop(&stack)->right == NULL || StackTop(&stack)->right == prev) {
struct TreeNode* node = StackTop(&stack);
StackPop(&stack);
(*a)[(*pi)++] = node->val; // 将节点值添加到结果数组
prev = node; // 更新上一个访问的节点
} else {
// 处理右子节点
current = StackTop(&stack)->right;
}
}
}
int treesize(struct TreeNode* root)
{
if(root==NULL)
{
return 0;
}
return 1+treesize(root->left)+treesize(root->right);
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
int count=treesize(root);
int *a=(int*)malloc(count*sizeof(int));
int pi=0;
postorder(root,&a,&pi);
*returnSize=pi;
return a;
}