二叉树的后序遍历 - 久染的小世界呀

一.后序遍历

方法一：非递归实现

主要思路：

取跟节点为目标节点，开始遍历
1.左孩子入栈 -> 直至左孩子为空的节点
2.栈顶节点的右节点为空或右节点被访问过 -> 节点出栈并访问他，将节点标记为已访问
3.栈顶节点的右节点不为空且未被访问，以右孩子为目标节点，再依次执行1、2、3

let postorderTraversal = function(root){
    const stack = []
    const result = []
    const last = null
    let current = root
    while(current || stack.length){
        while(current){
            stack.push(current)
            current = current.left
        }
        //获取父节点
        current = stack[stack.length - 1]
        if(!current.right || current.right == last){
            current = stack.pop();
            result.push(current)
            //标记已入栈
            last = current;
            //继续出栈
            current = null
        } else{
            current = current.right
        }
    }
}

方法二：递归实现

let preorderTraversal = function(root){
    let result = []
    if(root){
        preorderTraversal(root.left)
        preorderTraversal(root.right)
        result.push(root.val)
    }
    return result;
}