原题
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [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/
