145. 二叉树的后序遍历

题目描述

原题
给定一个二叉树,返回它的 后序 遍历。
示例:
1
输入: [1,null,2,3]
2
1
3
\
4
2
5
/
6
3
7
8
输出: [3,2,1]
Copied!
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

题解

递归

1
class Solution {
2
public List<Integer> postorderTraversal(TreeNode root) {
3
List<Integer> list = new ArrayList<>();
4
if(root != null){
5
list.addAll(postorderTraversal(root.left));
6
list.addAll(postorderTraversal(root.right));
7
list.add(root.val);
8
}
9
return list;
10
}
11
}
Copied!

迭代

1
class Solution {
2
public List<Integer> postorderTraversal(TreeNode root) {
3
LinkedList<Integer> list = new LinkedList<>();
4
if(root == null){
5
return list;
6
}
7
LinkedList<TreeNode> stack = new Stack<>();
8
stack.push(root);
9
while(!stack.isEmpty()){
10
//后序遍历 left right root
11
//root right left
12
TreeNode node = stack.pop();
13
list.addFirst(node.val);
14
if(node.left!=null){
15
stack.push(node.left);
16
}
17
if(node.right!=null){
18
stack.push(node.right);
19
}
20
}
21
return list;
22
}
23
}
Copied!
最近更新 6mo ago