1.题目:
给你一棵二叉树的根节点 root
,返回其节点值的后序遍历。
2.原理:
这里的遍历,是要存入到数组中,所以需要建立数组,这里传参有*returnSize,需要求节点个数,可以调用前面TreeSize函数,(小编前面树的实现里面有),这里要传入记录数组元素个数,后面运用递归,向下递归,直到空节点,当左右节点回退都为零,然后存入这个节点,直到回退到根节点。
3.整体代码:
/*** 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().*/
typedef struct TreeNode TreeNode;int TreeSize(TreeNode*root){if(root==NULL){return 0;}return 1+TreeSize(root->left)+TreeSize(root->right);}void PreOrder(TreeNode*root,int*arr,int*i)
{if(root==NULL){return;}PreOrder(root->left,arr,i);PreOrder(root->right,arr,i);arr[(*i)++]=root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*arr=(int*)malloc(sizeof(int)*(*returnSize));int num=0;PreOrder(root,arr,&num);return arr;
}