原题
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3] 1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解法
思想
- 递归
- 迭代（不同于前序遍历和中序遍历，后序遍历迭代更麻烦）
- 逆转前序遍历
代码
递归：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> ans = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root!=null){
postorderTraversal(root.left);
postorderTraversal(root.right);
ans.add(root.val);
}
return ans;
}
}
迭代：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode last = null;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
TreeNode temp = stack.peek();
//是否变到右子树
if (temp.right != null && temp.right != last) {
cur = temp.right;
} else {
list.add(temp.val);
last = temp;
stack.pop();
}
}
}
return list;
}
逆转前序遍历：（来源leetcode官方）
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollLast();
output.addFirst(node.val);
if (node.left != null) {
stack.add(node.left);
}
if (node.right != null) {
stack.add(node.right);
}
}
return output;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode145-%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e5%90%8e%e5%ba%8f%e9%81%8d%e5%8e%86/
相关推荐
-
leetcode1431-拥有最多糖果的孩子（儿童节快乐！）
原题 给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。 对每一个孩子，检查是否存在一种方案，将额...
-
leetcode983-最低票价
原题 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车...
-
剑指offer35-复杂链表的复制
原题（来源Leetcode） 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random ...
-
leetcode771-宝石与石头
原题 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。 J 中的字母不重复，J ...
-
leetcode200-岛屿数量
原题 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水...
-
leetcode1300-转变数组后最接近目标值的数组和
原题 给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 targe...
-
leetcode162-寻找峰值
原题 峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。 数组可能包含多个峰值，在这种情况...
-
leetcode123-买卖股票的最佳时机III
原题 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你...
-
leetcode26-删除排序数组中的重复项
原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空...
-
leetcode509-斐波那契数
原题 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0, F(1) ...
