LeetCode94：二叉树的中序遍历

😊1.题目

尝试一下该题

😉2.解法

1.递归

/*** 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().*/void Inorder(struct TreeNode* root,int *res, int* returnSize){if(root){Inorder(root->left, res, returnSize);res[(*returnSize)++] = root->val;Inorder(root->right,res,returnSize);}}
int* inorderTraversal(struct TreeNode* root, int* returnSize){*returnSize = 0;int *res = (int*)malloc(sizeof(int)*101);Inorder(root,res,returnSize);return res;
}

2.迭代

/*** 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().*/
#define MAX 101
typedef struct stack{int top;struct TreeNode *data[MAX];
}SqStack;SqStack* InitStack(){SqStack *S = (SqStack*)malloc(sizeof(SqStack));S->top = -1;return S;
}bool IsEmpty(SqStack *S){return S->top == -1;
}void push(SqStack *S, struct TreeNode *p){S->data[++S->top] = p;
}void pop(SqStack *S, struct TreeNode **p){*p = S->data[S->top--];
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = 0;int *res =(int*)malloc(sizeof(int)*101);SqStack *S;S= InitStack();struct TreeNode *cur = root;while(cur || !IsEmpty(S)){if(cur){push(S,cur);cur = cur->left;}else{pop(S,&p);res[(*returnSize)++] = cur->val;cur = cur->right;}}return res;}