145. 二叉树的后序遍历

题目描述

原题

给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

题解

递归

class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root != null){
list.addAll(postorderTraversal(root.left));
list.addAll(postorderTraversal(root.right));
list.add(root.val);
}
return list;
}
}

迭代

class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> list = new LinkedList<>();
if(root == null){
return list;
}
LinkedList<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
list.addFirst(node.val);
if(node.left!=null){
stack.push(node.left);
}
if(node.right!=null){
stack.push(node.right);
}
}
return list;
}
}