二叉树的后序遍历

后续遍历算法口诀：

对根节点的左子树进行后续遍历 对根节点的右子树进行后续遍历 访问根节点

const bt = { val: 1, left: { val: 2, left: { val: 4, left: null, right: null, }, right: { val: 5, left: null, right: null, }, }, right: { val: 3, left: { val: 6, left: null, right: null, }, right: { val: 7, left: null, right: null, }, }, };

递归版

const postorder = (root) => { if(!root) {return;} postorder(root.left) postorder(root.right) console.log(root.val) } postorder(bt)

非递归版

const postorder = (root) => { if(!root) {return;} const outputStack = [] const stack = [root] while(stack.length) { const n = stack.pop() outputStack.push(n) if(n.left) stack.push(n.left) if(n.right) stack.push(n.right) } while(outputStack.length) { const n = outputStack.pop(); console.log(n.val); } } postorder(bt) 4 5 2 6 7 3 1