数据结构--递归、非递归实现二叉树的中序遍历

1 中序遍历

完成

int* preorderTraversal(struct TreeNode* root, int* returnSize)

函数，使其可以实现前序遍历的功能

题目链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

1.1 递归实现

int getSize(struct TreeNode* root){
    if(root == NULL)
        return 0 ;
    return getSize(root->left) + getSize(root->right) + 1;
}
void inOrder(struct TreeNode* root , int* arr , int* idx){
    if(root){
        inOrder(root->left , arr , idx);
        arr[*idx] = root->val;
        (*idx)++;
        inOrder(root->right , arr , idx);
    }
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int sz = getSize(root);
    int* arr = (int*)malloc(sizeof(int)*sz);
    int idx = 0;
   inOrder(root , arr , &idx);
   *returnSize = idx;
   return arr ;
}
           

1.2 非递归实现

1.2.1 基本思想

• 以节点开始走最左路径，此路径上遇到的每一个节点首先入栈，但是不能访问
• 获取栈顶元素，访问栈顶元素
• 获取栈顶元素的右子树，继续执行第一步
• 结束：栈为空&&右子树为空

1.2.2 程序代码

引入栈的定义及接口：

typedef struct TreeNode* STDataType;
 typedef struct Stack {
	STDataType* data;  //数组
	int top;      //栈顶指针
	int capacity;    //数组的容量
}Stack;
//动态数组实现栈
void stackInit(Stack* st) {
	if (st == NULL)
		return;
	st->data = NULL;
	//栈中没有存储任何元素，栈顶指向-1
	st->top = -1;
	st->capacity = 0;
}

void checkCapacity(Stack* st) {
	if (st == NULL)
		return;
	//若数组存储满了，则进行扩容
	if (st->top == (st->capacity) - 1) {
		int newCapacity = st->capacity == 0 ? 1 : st->capacity * 2;
		//将st->data数组扩容到sizeof(STDataType)*newCapacity个字节大小
		st->data = (STDataType*)realloc(st->data, sizeof(STDataType)*newCapacity);
		st->capacity = newCapacity;
	}
}

void stackPush(Stack* st, STDataType val) {
	if (st == NULL)
		return;
	//检查栈是否满了
	checkCapacity(st);
	//进行入栈，栈顶+1 ，存入数据
	st->top++;
	st->data[st->top] = val;
}

void stackPop(Stack* st) {
	//若栈中无数据则进行返回
	if (st == NULL || st->top == -1) {
		return;
	}
	//栈顶-1
	st->top--;
}

//获取栈顶元素
STDataType stackTop(Stack* st) {
	//前提是栈中有有效元素
	return st->data[st->top];
}

//获取栈中的有效元素个数
int stackSize(Stack* st) {
	if (st == NULL)
		return 0;
	return (st->top) + 1;
}

//检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int stackEmpty(Stack* st) {
	if (st == NULL || st->top == -1)
		return 1;
	return 0;
}

//销毁栈
void stackDestroy(Stack* st) {
	free(st->data);
	st->data = NULL;
	st->top = -1;
	st->capacity = 0;
}
           

实现中序遍历：

int getSize(struct TreeNode* root) {
	if (root == NULL)
		return 0;
	return getSize(root->left) + getSize(root->right) + 1;
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
	int sz = getSize(root);
	int* arr = (int*)malloc(sizeof(int) * sz);
	int idx = 0;

	Stack st;
	stackInit(&st);
	while (root || !stackEmpty(&st)) {
        //访问最左路径
		while (root) {
			stackPush(&st, root);
			root = root->left;
		}
        //获取栈顶元素，访问右子树
		root = stackTop(&st);
		stackPop(&st);
        arr[idx] = root->val;
		idx++;
        root = root->right;
	}
	*returnSize = idx;
	return arr;
}