题解 | #二叉树的后序遍历-递归和非递归#

递归思想：左右中，注意递归出口，res全局性

function postorderTraversal( root ) {
    // write code here
    const res = [];
    postOrder(root,res);
    return res;
}
function postOrder(root,res){
    if(!root) return;
    postOrder(root.left,res);
    postOrder(root.right,res);
    res.push(root.val);
}
module.exports = {
    postorderTraversal : postorderTraversal
};

非递归思想：两个栈！类似先序遍历，先把根出栈并押入辅助栈，但是先序是先右进栈后左进栈；后序则是左进栈右进栈。

	let res = []
    if(!root) return res;
    let stk1 = [root];
    let stk2 = [];
    
    while(stk1.length){
        const n = stk1.pop();
        stk2.push(n.val);
        //此处与先序顺序相反
        if(n.left) stk1.push(n.left);
        if(n.right) stk1.push(n.right);
    }
    //console.log(stk2)
    while(stk2.length){
        res.push(stk2.pop());
    }
    return res;
}