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

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

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

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

示例:

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