给定一个二叉树的根节点root,返回它的中序遍历结果。
数据范围:树上节点数满足 ,树上每个节点的值满足
进阶:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
{1,2,#,#,3}
[2,3,1]
{}
[]
{1,2}
[2,1]
{1,#,2}
[1,2]
树中节点数目在范围 [0, 100] 内树中的节点的值在[-100,100]以内
void inorderTraver(struct TreeNode* root, int* res, int* StaticReturnSize ) { if(root->left!=NULL) inorderTraver(root->left, res, StaticReturnSize); res[(*StaticReturnSize)++] = root->val; if(root->right!=NULL) inorderTraver(root->right, res, StaticReturnSize); } int* inorderTraversal(struct TreeNode* root, int* returnSize ) { static int res[1000]={0}, StaticReturnSize=0; if(root==NULL) return NULL; inorderTraver(root, res, &StaticReturnSize); *returnSize = StaticReturnSize; return res; }
void inOrder(struct TreeNode* root, int** a, int* count) { if (root != NULL) { inOrder(root->left, a, count); (*a)[(*count)++] = root->val; inOrder(root->right, a, count); } } int* inorderTraversal(struct TreeNode* root, int* returnSize) { int* a = malloc(sizeof(int) * 1001); int count = 0; inOrder(root, &a, &count); *returnSize = count; int* result = malloc(sizeof(int) * count); memcpy(result, a, sizeof(int) * count); free(a); return result; }
struct TreeNode* stack[1000]; //作为栈使用,栈底是下标0 int stack_top = -1; int* inorderTraversal(struct TreeNode* root, int* returnSize ) { // write code here int* ret_arr = NULL; *returnSize = 0; if (!root) return ret_arr; int tmp[1000] = {0}; int i = 0; while (root) { if (root->left) { stack[++stack_top] = root; root = root->left; stack[stack_top]->left = NULL; //一定要NULL,否则会死循环 } else { tmp[i++] = root->val; if(root->right) root = root->right; else { if (stack_top >= 0) { printf("stack_top: %d\n",stack_top); root = stack[stack_top--]; } else root = NULL; } } } *returnSize = i; ret_arr = malloc(sizeof(int) * i); if (!ret_arr) return NULL; memset(ret_arr, 0, i * sizeof(int)); for (int j = 0; j < i; j++) ret_arr[j] = tmp[j]; return ret_arr; }
int pre_sequence[1000] = {0}, i = 0; int* inorderTraversal(struct TreeNode* root, int* returnSize ) { int top_stack = -1; struct TreeNode* stack[1000], *p; if(root != NULL){ stack[++top_stack] = root; } while (top_stack != -1) { if(stack[top_stack]->right != NULL){ stack[top_stack + 1] = stack[top_stack]; stack[top_stack] = stack[top_stack]->right; stack[++top_stack]->right = NULL; } if(stack[top_stack]->left != NULL){ stack[top_stack + 1] = stack[top_stack]->left; stack[top_stack++]->left = NULL; } else { pre_sequence[i++] = stack[top_stack]->val; top_stack--; } } *returnSize = i; return pre_sequence; }
static int count = 0; void inOrder(struct TreeNode* root,int *a){ if(root != NULL){ inOrder(root->left, a); a[count++] = root->val; inOrder(root->right, a); } } int* inorderTraversal(struct TreeNode* root, int* returnSize ) { int *a = (int*)malloc(sizeof(int)*1001); inOrder(root, a); *returnSize = count; return a; // write code here }