网络异常，图片无法展示
|
「这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战」
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1] 复制代码
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
题解1
首先我们用本题所说的很简单的方法，递归完成本题
解题思路如下：
- 当根结点为空的时候，递归终止
- 递归的处理左子树、右子树，最后将当前结点的值
push到结果数组
代码如下：
var postorderTraversal = function(root) { const res = []; function postorder(root){ if(root === null) return; postorder(root.left); postorder(root.right); res.push(root.val); } postorder(root); return res; }; 复制代码
题解2
那怎么通过迭代算法完成二叉树的后序遍历呢？
解题思路如下：
- 首先初始化一个栈和一个结果数组
- 当存在右子树的时候，一直向下找右子树，该过程中将每个结点压入栈中，并将它的值倒序的插入结果数组
- 当找到最右边的右子树之后，将压入栈的元素取出，并将root指向它的左子树
- 此时如果左子树存在，则左子树的值会被插入到结果数组的头部
- 如此一个一个的三元组处理完成，直到根结点，则会进入左子树处理
- 这个过程，结点值插入的顺序是 根 右 左
- 因为节点的值每次是插入结果数组头部的，所以结果数组值的顺序为左 右 根
- 最后返回结果数组即可
代码如下：
var postorderTraversal = function(root) { // 初始化栈和结果数组 const stack =[], res = []; while (root || stack.length){ // 一直向下找右子树 while(root){ // 将每个节点压入栈中 stack.push(root); // 过程中将每个结点的值倒序的插入结果数组 res.unshift(root.val); root = root.right; } // 将压入栈的元素取出，并将root指向它的左子树 // 此时如果左子树存在，则左子树的值会被插入到结果数组的头部 root = stack.pop().left; } // 如此一个一个的三元组处理完成，直到根结点，则会进入左子树处理 // 这个过程，结点值插入的顺序是 根 右 左 // 因为节点的值每次是插入结果数组头部的，所以结果数组值的顺序为左 右 根 return res; }; 复制代码
至此我们就完成了 leetcode-145-二叉树的后序遍历
如有任何问题或建议，欢迎留言讨论！
