package question;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/*
 @author: Roderland
 @create: 2020年09月29日---16:52
*/
public class Question145 {
 public static void main(String[] args) {
 //3,5,1,6,2,0,8,null,null,7,4
 TreeNode t1 = new TreeNode(3);
 TreeNode t2 = new TreeNode(5);
 TreeNode t3 = new TreeNode(1);
 TreeNode t4 = new TreeNode(6);
 TreeNode t5 = new TreeNode(2);
 TreeNode t6 = new TreeNode(0);
 TreeNode t7 = new TreeNode(8);
 TreeNode t8 = new TreeNode(7);
 TreeNode t9 = new TreeNode(4);
 t1.left=t2;
 t1.right=t3;
 t2.left=t4;
 t2.right=t5;
 t5.left=t8;
 t5.right=t9;
 t3.left=t6;
 t3.right=t7;
 new Question145().postorderTraversal(t1).forEach(System.out::print);
 }
 public List<Integer> postorderTraversal(TreeNode root) {
 List<Integer> res = new LinkedList<>();
 Deque<TreeNode> deque = new LinkedList<>();
 TreeNode prev = null;
 while (root!=null || !deque.isEmpty()) {
 while (root!=null) {
 deque.offerLast(root);
 root=root.left;
 }
 root=deque.pollLast();
 if (root.right!=null && root.right!=prev) {
 deque.offerLast(root);
 root=root.right;
 } else {
 res.add(root.val);
 prev=root;
 root=null;
 }
 }
 return res;
 }
}