怎样同时非递归进行二叉树的前、中、后序
实现二叉树先序,中序和后序遍历
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;
}
}

