给定一个二叉树,返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
数据范围:二叉树的节点数量满足 ,二叉树节点的值满足 ,树的各节点的值各不相同
样例图
void postorderTraver(struct TreeNode* root, int* res, int* StaticReturnSize ) { if(root->left!=NULL) postorderTraver(root->left, res, StaticReturnSize); if(root->right!=NULL) postorderTraver(root->right, res, StaticReturnSize); res[(*StaticReturnSize)++] = root->val; } int* postorderTraversal(struct TreeNode* root, int* returnSize ) { static int res[1000]={0}, StaticReturnSize=0; if(root==NULL) return NULL; postorderTraver(root, res, &StaticReturnSize); *returnSize = StaticReturnSize; return res; }
void postOrder(struct TreeNode* root, int** a, int* count) { if (root != NULL) { postOrder(root->left, a, count); postOrder(root->right, a, count); (*a)[(*count)++] = root->val; } } int* postorderTraversal(struct TreeNode* root, int* returnSize) { int* a = malloc(sizeof(int) * 1001); int count = 0; postOrder(root, &a, &count); *returnSize = count; int* result = malloc(sizeof(int) * count); memcpy(result, a, sizeof(int) * count); free(a); return result; }
int count=0; int arr[101]; void postOrder(struct TreeNode*root,int*arr) { if(root) { postOrder(root->left,arr); postOrder(root->right,arr); arr[count++]=root->val; } } int* postorderTraversal(struct TreeNode* root, int* returnSize ) { // write code here postOrder(root,arr); *returnSize=count; return arr; }方法二:栈
struct TreeNode*stack[100]; int arr[101]; int count=0; int top=-1; //记录上一个访问的节点 struct TreeNode* prev = NULL; //入栈 void push(struct TreeNode*node) { stack[++top]=node; } //出栈 struct TreeNode* pop(void) { return stack[top--]; } //后序遍历 左->右->根 //用栈实现,先进后出 int* postorderTraversal(struct TreeNode* root, int* returnSize ) { // write code here if(!root) { *returnSize=0; return NULL; } while(root||top!=-1) { while(root) { push(root); root=root->left; } root=stack[top]; //如果栈顶元素的右节点为空或者已经访问过,则可以访问根节点 if (!root->right || root->right == prev) { //根节点存在,保存val arr[count++] = root->val; //记录上一个访问的节点 prev = root; //栈顶元素出栈 root = pop(); //将根节点置为NULL,避免再次访问 root = NULL; } else { //开始遍历右节点 root = root->right; } } *returnSize=count; return arr; }
struct TreeNode* stack[100]; //作为栈使用,栈底是下标0 int stack_top = -1; int* postorderTraversal(struct TreeNode* root, int* returnSize ) { // write code here int* ret_arr = NULL; *returnSize = 0; if (!root) return ret_arr; int tmp[100] = {0}; int i = 0; struct TreeNode* l_ptr = NULL; struct TreeNode* r_ptr = NULL; while (root) { if (root->right || root->left) { stack[++stack_top] = root; l_ptr = root->left; r_ptr = root->right; stack[stack_top]->left = NULL; stack[stack_top]->right = NULL; if(r_ptr) stack[++stack_top] = r_ptr; if(l_ptr) root= l_ptr; else { if (stack_top >= 0) root = stack[stack_top--]; else root = NULL; }; } else { tmp[i++] = root->val; if (stack_top >= 0) 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 postArr[100]; void postTraversal(struct TreeNode* root, int* returnSize, int* p){ if(root != NULL){ postTraversal(root->left, returnSize, p); postTraversal(root->right, returnSize, p); p[(*returnSize)++] = root->val; } } int* postorderTraversal(struct TreeNode* root, int* returnSize ) { *returnSize = 0; postTraversal(root, returnSize, postArr); return postArr; }
static int count=0; int TreeSize(struct TreeNode* root) { if(!root) return 0; return TreeSize(root->left)+TreeSize(root->right)+1; } void PostOrderTree(struct TreeNode* root,int* arr) { if(root) { PostOrderTree(root->left, arr); PostOrderTree(root->right, arr); arr[count++]=root->val; } } int* postorderTraversal(struct TreeNode* root, int* returnSize ) { int num=TreeSize(root); int* arr=(int*)malloc(sizeof(int)*num); *returnSize=num; PostOrderTree(root,arr); return arr; }
typedef struct TreeNode TreeNode; void Last(TreeNode *root,int *ret,int *retSize) { if(!root) { return; } Last(root->left,ret,retSize); Last(root->right,ret,retSize); ret[(*retSize)++] = root->val; } int* postorderTraversal(struct TreeNode* root, int* returnSize ) { // write code here int *ret = (int *)malloc(sizeof(int)*101); *returnSize = 0; Last(root,ret,returnSize); return ret; }