怎样同时非递归进行二叉树的前、中、后序
实现二叉树先序,中序和后序遍历
http://www.nowcoder.com/questionTerminal/a9fec6c46a684ad5a3abd4e365a9d362
前序和中序可以弄在一个循环里,但是后序我是真不知道怎搞在一个循环里,只能分开写,求大佬指教
import java.util.*; public class Solution { public int[][] threeOrders (TreeNode root) { List<Integer> front = new ArrayList<>(); List<Integer> mid = new ArrayList<>(); List<Integer> back = backTravel(root); LinkedList<TreeNode> queue = new LinkedList<>(); TreeNode cur = root; TreeNode last = null; // 前序+中序 while(cur != null || !queue.isEmpty()) { if(cur != null) { front.add(cur.val); queue.push(cur); cur = cur.left; } else { cur = queue.pop(); mid.add(cur.val); cur = cur.right; } } int[][] res = {front.stream().mapToInt(Integer::valueOf).toArray(), mid.stream().mapToInt(Integer::valueOf).toArray(), back.stream().mapToInt(Integer::valueOf).toArray()}; return res; } // 后序遍历 private List<Integer> backTravel(TreeNode root){ List<Integer> back = new ArrayList<>(); LinkedList<TreeNode> queue = new LinkedList<>(); TreeNode cur = root; TreeNode last = null; while(cur != null || !queue.isEmpty()) { if(cur != null) { queue.push(cur); cur = cur.left; } else { cur = queue.peek(); if (cur.right == null || cur.right == last) { back.add(cur.val); queue.pop(); last = cur; cur = null; } else { cur = cur.right; } } } return back; } }