递归和迭代实现二叉树后序遍历-一一网

这是我参与更文挑战的第7天，活动详情查看：更文挑战。

题目：145.二叉树的后序遍历

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

示例:

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归实现

后续遍历：左、右、根。

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    if(!root)return []
    const leftResult = postorderTraversal(root.left)
    const rightResult = postorderTraversal(root.right)
    return [...leftResult,...rightResult,root.val]
};
复制代码

迭代实现方法一

后续遍历：左、右、根。
用栈来存储遍历过但是目前还不能放入结果的节点。
1一直访问左子节点，直到叶子节点。中途节点存入栈中。叶子节点放入结果中。
2出栈。把当前的节点的左子节点置空。因为左子节点已经放入结果中了。
3对当前的节点访问右节点，并把当前的节点再次存入栈中。
4右节点再来这一边流程，直到右节点放入结果里。对右节点的父节点，把父节点的右节点置空。这时候就能把父节点放入结果中了。

后续遍历的复杂之处是对一个父节点进行了2次入栈出栈操作。第一次获取它的右子节点，第二次真正访问它。
这个思路从别的大佬那里看到的，很棒诶！

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    if(!root)return []
    //迭代实现
    const result = []
    const stack = []
    while(root || stack.length){
        if(root.left){
            stack.push(root)
            root = root.left
        }else if(root.right){
            stack.push(root)
            root = root.right
        }else{
            result.push(root.val)
            root = stack.pop()
            if(root && root.left){root.left = null}
            else if(root && root.right){root.right = null}
        }
    }
    return result
};
复制代码

迭代实现方法二

1后续遍历：左、右、根，和前序遍历根左右，除了根的位置不一样，左右的顺序是一样的。
2可以参考前序遍历的方法。先在结果中放入根节点。后面再放入子节点的结果。这样需要每次都插入到前面。
3为了保证左子树的结果是插入到最前面的。因此先入栈右节点，再入栈左节点。

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const postorderTraversal = root => {
    let res = [], stack = []
    while (root || stack.length) {
        res.unshift(root.val)
        if(root.left)stack.push(root.left)
        if(root.right)stack.push(root.right)
        root = stack.pop()
    }
    return res
}
复制代码