145. Binary Tree Postorder Traversal（二叉树后序遍历）

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],

return [3,2,1].

递归：

 1 class Solution {
 2     List<Integer> res = new ArrayList<Integer>();
 3     public List<Integer> postorderTraversal(TreeNode root) {
 4         help(root);
 5         return res;
 6     }
 7     private void help(TreeNode root){
 8         if(root == null) return ;
 9         help(root.left);
10         help(root.right);
11         res.add(root.val);
12     }
13 }

非递归：

终极版

 1 class Solution {
 2     public List<Integer> postorderTraversal(TreeNode root) {
 3         Stack<TreeNode> s =  new Stack<TreeNode>();
 4         List<Integer> res = new ArrayList<Integer>();
 5         while(root!=null||!s.isEmpty()){
 6             while(root!=null){
 7                 s.push(root);
 8                 res.add(0,root.val);
 9                 root = root.right;
10             }
11             
12             if(!s.isEmpty()){
13                 root = s.pop();
14                 root = root.left;
15             }
16         }
17         return res;
18     }
19 }

跟前序遍历差不多，stack 保存左子树，向右遍历，反向保存res.

 1 class Solution {
 2     List<Integer> res = new ArrayList<Integer>();
 3     public List<Integer> postorderTraversal(TreeNode root) {
 4         Stack<TreeNode> stack = new Stack<TreeNode>();
 5         TreeNode cur = root;
 6         while(cur!=null || !stack.isEmpty()){
 7             while(cur!=null){
 8                 res.add(0,cur.val);
 9                 stack.push(cur.left);
10                 cur = cur.right;
11             }
12             cur = stack.pop();
13         }
14         return res;
15     }
16 }