[TOC]

前序遍历_非递归

public class 前序遍历_非递归 {
// 非递归
private void pre(Node root) {
List<Integer> list = new LinkedList<>();
Stack<Node> stack = new Stack<>();
stack.add(root);
while (!list.isEmpty() || root != null) {
while (root != null) {
stack.add(root);
list.add(root.data);
root = root.left;
}
while (!stack.isEmpty()) {
root = stack.pop().right;
}
}
System.out.println(Arrays.toString(new List[] {list}));
}
// 更简洁的方式
private void pre2(Node root) {
if (root == null) {
return;
}
List<Integer> list = new LinkedList<>();
Stack<Node> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
list.add(node.data);
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
stack.add(node.left);
}
}
System.out.println(Arrays.toString(new List[] {list}));
}

中序遍历_非递归

private void mid(Node root) {
List<Integer> list = new LinkedList<>();
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.add(root);
root = root.left;
}
Node node = stack.pop();
list.add(node.data);
root=node.right;
}
System.out.println(Arrays.toString(new List[] {list}));
}

后序遍历_非递归

public class 后序遍历_非递归 {

private void last(Node root) {
List<Integer> list = new LinkedList<>();
Stack<Node> stack = new Stack();
if (root == null) {
return;
}
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
list.add(0, root.data);
if (root.left != null) stack.push(root.left);
if (root.right != null) stack.push(root.right);
}
}

public static void main(String[] args) {}
}