前序遍历-每日算法：二叉树的后序遍历

回复交流，加入前端编程面试算法每日一题群

面试官也在看的前端面试资料

给定一个二叉树，返回它的 后序遍历。

示例:

输入: [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

htebazile普通用户

收藏 海报 链接