成为VIP
回复交流，加入前端编程面试算法每日一题群
面试官也在看的前端面试资料
给定一个二叉树，返回它的 后序遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [3,2,1]
进阶:递归算法很简单，你可以通过迭代算法完成吗？
递归实现
// 后序遍历
const postorderTraversal = function(root) {
let result = []
var postorderTraversalNode = (node) => {
if(node) {
// 先遍历左子树
postorderTraversalNode(node.left)
// 再遍历右子树
postorderTraversalNode(node.right)
// 最后根节点
result.push(node.val)
}
}
postorderTraversalNode(root)
return result
};
迭代实现
解题思路： 后序遍历与前序遍历不同的是：
如果我们把前序遍历的 list.push(node.val) 变更为 list.unshift(node.val) （遍历结果逆序），那么遍历顺序就由 根左右 变更为 右左根
然后我们仅需将 右左根 变更为 左右根 即可完成后序遍
// 后序遍历
const postorderTraversal = (root) => {
const list = [];
const stack = [];
// 当根节点不为空的时候，将根节点入栈
if(root) stack.push(root)
while(stack.length > 0) {
const node = stack.pop()
// 根左右=>右左根
list.unshift(node.val)
// 先进栈左子树后右子树
// 出栈的顺序就变更为先右后左
// 右先头插法入list
// 左再头插法入list
// 实现右左根=>左右根
if(node.left !== null) {
stack.push(node.left)
}
if(node.right !== null) {
stack.push(node.right)
}
}
return list
}
复杂度分析：
空间复杂度：O(n)
时间复杂度：O(n)
最后
欢迎关注「三分钟学前端」前序遍历，回复「交流」自动加入前端三分钟进阶群，每日一道编程算法面试题（含解答）前序遍历，助力你成为更优秀的前端开发！
限时特惠：本站每日持续更新海量展厅资源，一年会员只需29.9元，全站资源免费下载
站长微信：zhanting688
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
