/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public List<Integer> postorderTraversal(TreeNode root) {

LinkedList<Integer> res = new LinkedList<>();

if(root == null) return res;

Stack<TreeNode> stack = new Stack<>();//lifo

stack.push(root);

while(!stack.isEmpty()){

TreeNode cur = stack.pop();

res.addFirst(cur.val);// 1.root 2. right->root 3. left-> right-> root.

if(cur.left!=null) stack.push(cur.left);

if(cur.right!=null) stack.push(cur.right);

}

return res;

}

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public List<Integer> postorderTraversal(TreeNode root) {

List<Integer> res = new ArrayList<>();

if(root == null) return res;

helper(root, res);

return res;

}

private void helper(TreeNode root, List<Integer> res){

if(root == null) return;

helper(root.left, res);

helper(root.right, res);

res.add(root.val);

}

}

}