来源Leetcode第145题二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
递归
递归顺序左右根就完事了嗷。
1
2
3
4
5
6
7
8
9
10
11
| List<Integer> ans = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null)
return ans;
if (root.left != null)
postorderTraversal(root.left);
if (root.right != null)
postorderTraversal(root.right);
ans.add(root.val);
return ans;
}
|
BFS+倒序输出 = 后序？
再改前序遍历的代码改的时候发现直接reverse输出左右子树的顺序不对，于是将入栈顺序改了就行了。。。
原理就是这样的遍历顺序是根右左，而后序遍历是左右根，因而翻转就是左右根了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null)
return ans;
stack.add(root);
while(!stack.empty()){
TreeNode temp = stack.pop();
ans.add(temp.val);
if(temp.left != null)
stack.add(temp.left);
if(temp.right != null)
stack.add(temp.right);
}
Collections.reverse(ans);
return ans;
}
|