问题：

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

For example:

Given binary tree {1,#,2,3},

   1    \     2    /   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

解决：

① 后根遍历，递归方法。

/**

 * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */

public class Solution {//1ms

    public List<Integer> postorderTraversal(TreeNode root){         List<Integer> res = new ArrayList<>();         postorder(root,res);         return res;     }     public void postorder(TreeNode root,List<Integer> res){         if (root == null) return;         postorder(root.left,res);         postorder(root.right,res);         res.add(root.val);     } }

② 非递归方法，使用栈，后根遍历的顺序是：左-->右-->根，可以先根据：根-->右-->左的顺序来遍历，然后使用链表保存的结果是反序存放的，所以只需要将结果插入到链表的头部即可。

class Solution { //1ms

    public List<Integer> postorderTraversal(TreeNode root) {         List<Integer> res = new ArrayList<>();         Stack<TreeNode> stack = new Stack<>();         if(root != null){             stack.push(root);             while(! stack.isEmpty()){                 TreeNode cur = stack.pop();                 res.add(0,cur.val);                 if(cur.left != null) stack.push(cur.left);                 if(cur.right != null) stack.push(cur.right);             }         }         return res;     } }

③ 非递归方法，使用stack。

【注】

首先要搞清楚先序、中序、后序的非递归算法共同之处：用栈来保存先前走过的路径，以便可以在访问完子树后,可以利用栈中的信息,回退到当前节点的双亲节点,进行下一步操作。

后序遍历的非递归算法是三种顺序中最复杂的，原因在于，后序遍历是先访问左、右子树,再访问根节点，而在非递归算法中，利用栈回退到时，并不知道是从左子树回退到根节点，还是从右子树回退到根节点，如果从左子树回退到根节点，此时就应该去访问右子树，而如果从右子树回退到根节点，此时就应该访问根节点。所以相比前序和后序，必须得在压栈时添加信息，以便在退栈时可以知道是从左子树返回，还是从右子树返回进而决定下一步的操作。

在出栈的时候需要分情况一下：

1）如果当前栈顶元素的右结点存在并且还没访问过（也就是右结点不等于上一个访问结点），那么就把当前结点移到右结点继续循环； 2）如果栈顶元素右结点是空或者已经访问过，那么说明栈顶元素的左右子树都访问完毕，应该访问自己继续回溯了。

class Solution {//2ms

    public List<Integer> postorderTraversal(TreeNode root) {         List<Integer> res = new ArrayList<>();         Stack<TreeNode> stack = new Stack<>();         TreeNode pre = null;         while(root != null || ! stack.isEmpty()){             if(root != null){                 stack.push(root);                 root = root.left;             }else{                 TreeNode cur = stack.peek();                 if (cur.right != null && pre != cur.right) {                     root = cur.right;                 }else{                     stack.pop();                     res.add(cur.val);                     pre = cur;                 }             }         }         return res;     } }

④ 还有一个Morris方法