二叉树的后序遍历

[ChuChencheng]

问题

LeetCode 145

解

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    const result = []
    const traverse = (node) => {
        if (node) {
            if (node.left) traverse(node.left)
            if (node.right) traverse(node.right)
            result.push(node.val)
        }
    }
    traverse(root)
    return result
};

非递归1

与前序、中序不同，使用一个变量来记录栈顶节点的右子节点是否被访问过了，且在判断是否访问过之前，不执行出栈操作；如果栈顶节点没有右子节点或者右子节点被访问过，则出栈。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    const result = []
    const stack = []
    let seen = null
    let node = root
    while (node || stack.length) {
        while (node) {
            stack.push(node)
            node = node.left
        }
        // 此处因为中间节点可能还不能 push 到 result 中，因此不用 pop
        const last = stack[stack.length - 1]
        if (!last.right || last.right === seen) {
            // 如果没有右子节点或者右子节点已经遍历过了
            result.push(last.val)
            seen = last
            stack.pop()
        } else {
            node = last.right
        }
    }
    return result
};

非递归2

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    const result = []
    if (!root) return result
    const stack = [root]
    while (stack.length) {
        const node = stack.pop()
        if (node.left) stack.push(node.left)
        if (node.right) stack.push(node.right)
        result.unshift(node.val)
    }
    return result
};