东莞网站建设信科分公司手机百度网页版

本篇博客会讲解力扣“145. 二叉树的后序遍历”的解题思路，这是题目链接。

本题的思路是：

1. 先创建一个数组，用来存储二叉树后序遍历的结果。数组的大小跟树的结点个数有关。树的结点个数可以使用递归实现，即总个数=左子树结点个数+右子树结点个数+1。
2. 接着实现后序遍历。先遍历左子树，再遍历右子树，最后遍历根节点，把遍历的结果存储在返回数组里。

int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}void _postorderTraversal(struct TreeNode* root, int* ret, int* pi)
{if (root == NULL){return;}// 左子树 右子树 根_postorderTraversal(root->left, ret, pi);_postorderTraversal(root->right, ret, pi);ret[(*pi)++] = root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize){*returnSize = TreeSize(root);int* ret = (int*)malloc(sizeof(int) * *returnSize);int i = 0;_postorderTraversal(root, ret, &i);return ret;
}

总结

后序遍历：先遍历左子树，再遍历右子树，最后遍历根结点。

感谢大家的阅读！