【数据结构与算法】后续遍历的非递归实现

回忆一下递归实现

/**
/**
 * 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) {
	var retArr = []
	if (!root) return retArr
	var helpFunc = (r)=>{
		if (!r) return 
		helpFunc(r.left)
		helpFunc(r.right)
		retArr.push(r.val)
	}
	helpFunc(root)
	return retArr
}

用模拟栈来实现（方法一） 逆向

var postorderTraversal = function(root) {
    if(!root) return []
    let cur = root
    var stack = []
    var retArr = []
    while(stack.length !== 0 || cur){
        // 右节点入栈
        if (cur) {
            stack.push(cur)
            retArr.push(cur.val)
            cur = cur.right
        }   else {
            var tmp = stack.pop()
            cur = tmp.left
        }

    }
    return retArr.reverse()
 }

用模拟栈来实现（方法二 ） （单栈）

var postorderTraversal = function(root) {
    if(!root) return []
    let cur = root
    var stack = []
    var retArr = []
    var r = null // 记录访问过的子节点
    while(stack.length !== 0 || cur){
        // 左节点入栈
        if (cur) {
            stack.push(cur)
            cur = cur.left
        }   else {

            cur = stack[stack.length - 1] // 读取栈顶元素，非弹出
            // 如果右子树存在，并且没有被访问
            if (cur.right && cur.right !=r) {
                cur = cur.right
            } else {
                // 弹出并访问
                var tm = stack.pop()
                retArr.push(tm.val)
                r = cur
                cur = null
            }
        }

    }
    return retArr
 }

根左右 【前序】
左根右 【中序】

根右左 【后序–逆向】
右根左 【中序–逆向】