网站建设制作北京网站建设优化

题目描述：给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历

解题思路：

迭代法：

后序（左右根）

先序是根左右 后序是左右根 后序翻转一下就是 根右左

所以后序的结果实际就是 先序的方法，调换左右节点的访问顺序

解法一（递归）：

const postOrder = (root) => {const traverse = (curNode,res) => {if(curNode === null) {return;}traverse(curNode.left,res);traverse(curNode.right,res);res.push(curNode.value);}let res = [];traverse(root);return res;
}

用时：

// Your runtime beats 83.33 % of typescript submissions

// Your memory usage beats 5.55 % of typescript submissions (51.7 MB)

解法二（迭代法）：

let postOrder = (root) => {if(root === null) {return [];}let stack = [root];let res = [];while(stack.length){let cur = stack.pop();res.push(cur.val);if(cur.left) {stack.push(cur.left);}if(cur.right) {stack.push(cur.right)}}return res.reverse();
}

用时：

// Your runtime beats 82.48 % of typescript submissions

// Your memory usage beats 5.12 % of typescript submissions (51.7 MB)