Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3]
,
1
\
2
/
3
return [3,2,1]
.
递归:
class Solution {
List<Integer> res = new ArrayList<Integer>();
public List<Integer> postorderTraversal(TreeNode root) {
help(root);
return res;
}
private void help(TreeNode root){
if(root == null) return ;
help(root.left);
help(root.right);
res.add(root.val);
}
}
非递归:
终极版
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack<TreeNode>();
List<Integer> res = new ArrayList<Integer>();
while(root!=null||!s.isEmpty()){
while(root!=null){
s.push(root);
res.add(0,root.val);
root = root.right;
} if(!s.isEmpty()){
root = s.pop();
root = root.left;
}
}
return res;
}
}
跟前序遍历差不多 ,stack 保存左子树,向右遍历,反向保存res.
class Solution {
List<Integer> res = new ArrayList<Integer>();
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
res.add(0,cur.val);
stack.push(cur.left);
cur = cur.right;
}
cur = stack.pop();
}
return res;
}
}