代码随想录day17(2)二叉树:二叉树的后序遍历(leetcode145)

时间:2024-03-13 16:13:09

题目要求:实现二叉树的后序遍历。

思路:对于二叉树的后序遍历,通常可以使用递归算法与非递归(迭代)算法两种。

对于递归算法,我们首先应该确定递归函数的参数以及返回值,其次应该确定终止条件,最后再确定单层递归的逻辑。二叉树的参数一般包括根节点以及结果数组,终止条件应为此时结点为空结点,应该返回到上一层。单层逻辑应该为递归访问其左右孩子结点,然后再将元素push到结果数组中。

对于非递归算法,我们应该使用栈来代替递归的过程。对于后序遍历,我们期望得到的序列是左右中,我们可以先将先序遍历的中左右调整为中右左,最后反转result数组为左右中即可。

leetcode实战:

代码实现:

递归算法:

非递归算法: