题目
给定一个 N 叉树,返回其节点值的后序遍历。
例如,给定一个
3叉树
:返回其后序遍历:
[5,6,3,2,4,1]
.说明: 递归法很简单,你可以使用迭代法完成此题吗?
思路一: 递归法
正如题目中所言, 递归法确实很简单, 利用二叉树中的”左-右-根”顺序进行推广, 即先遍历子树, 最后将根的值放入list
中即可
1 | /* |
思路二: 迭代
树的遍历除了用递归实现, 还可以用迭代实现.
- 先将根结点入栈
- 取出栈中结点, 并将结点的值放入结果队列的头部, 将其子结点按左到右的顺序入栈
- 重复第二步直至栈为空
1 | class Solution { |