|
分为递归和循环两种方式：
循环为模拟递归的入栈出栈的操作过程。
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Solution5_2 {
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {}
public TreeNode(int val) { this.val = val; }
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null){
return new ArrayList<>();
}
List<Integer> list = new ArrayList<>();
list.add(root.val);
List<Integer> list1 = preorderTraversal(root.left);
list.addAll(list1);
List<Integer> list2 = preorderTraversal(root.right);
list.addAll(list2);
return list;
}
public List<Integer> r = new ArrayList<>();
public List<Integer> preorderTraversal2(TreeNode root) {
preorder(root);
return r;
}
//返回值为void
public void preorder(TreeNode root) {
if (root == null){
return;
}
r.add(root.val);
preorder(root.left);
preorder(root.right);
}
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null){
return new ArrayList<Integer>();
}
List<Integer> list1 = inorderTraversal(root.left);
List<Integer> list = new ArrayList<>();
list.addAll(list1);
list.add(root.val);
List<Integer> list2 = inorderTraversal(root.right);
list.addAll(list2);
return list;
}
public List<Integer> inorderTraversal2(TreeNode root) {
inorder(root);
return r;
}
public void inorder(TreeNode root){
if (root == null){
return;
}
inorder(root.left);
r.add(root.val);
inorder(root.right);
}
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null){
return new ArrayList<>();
}
List<Integer> list1 = postorderTraversal(root.left);
List<Integer> list2 = postorderTraversal(root.right);
List<Integer> list = new ArrayList<>();
list.addAll(list1);
list.addAll(list2);
list.add(root.val);
return list;
}
/**
* 思路：
* 模拟递归方法的入栈出栈的过程
*
* 栈帧中元素
* 1.结点
* 2.结点的状态
*
* 过程：
* 1.将该结点入栈（此时该结点为栈顶）
* 2.打印该结点
* 3.左子树入栈出栈，直到左子树完毕，该结点为栈顶
* 4.右子树入栈出栈，直到右子树完毕，该结点为栈顶
* 5.该结点出栈
* 6.循环1到5，直到栈为空
* @return
*/
public class StackFrame {
public TreeNode node;
/**
* 首次入栈，状态为1（该元素为栈顶）
* 左子树遍历完，状态为2（该元素为栈顶）
* 右子树遍历完，状态为3（该元素为栈顶）
*/
public int state;
public StackFrame(TreeNode node, int state) {
this.node = node;
this.state = state;
}
}
public List<Integer> preorderTraversal_foreach(TreeNode root) {
List<Integer> r = new ArrayList<>();
if (root == null){
return r;
}
//首先创建栈，用于模拟递归入栈出栈的过程
Stack<StackFrame> stack = new Stack<>();
TreeNode p = root;
//将最小树不停的循环
while (true){
//将该元素入栈，一路向左
while (p != null){
//先入栈，再打印
stack.push(new StackFrame(p, 1));
r.add(p.val);
p = p.left;
}
// 再次回来时，状态要变成2，
// 但是同一个结点，有三次为栈顶元素，只有当前元素的状态为1，才可以变成2，状态为3时，不可以修改为2
if (stack.peek().state == 1){
stack.peek().state = 2;
//开始遍历右侧
p = stack.peek().node.right;
continue;
}
//右侧遍历结束
if (stack.peek().state == 2){
stack.peek().state = 3;
stack.pop();
if (stack.isEmpty()){
break;
}
}
}
return r;
}
/**
* 思路：
* 1.入栈，打印，状态为1
* 2.如果状态为2，则出栈
* 3.否则，将状态改为2，并且将结点改为当前结点的右子结点
* @param root
* @return
*/
public List<Integer> preorderTraversal_foreach2(TreeNode root) {
List<Integer> r = new ArrayList<>();
Stack<StackFrame> stack = new Stack<>();
TreeNode p = root;
while (true){
while (p != null){
stack.push(new StackFrame(p, 1));
r.add(p.val);
p = p.left;
}
//第三次回来时，状态由2->3，并且弹出栈
while (!stack.isEmpty() && stack.peek().state == 2){
stack.peek().state = 3;
stack.pop();
}
if (stack.isEmpty()){
break;
}
stack.peek().state = 2;
p = stack.peek().node.right;
}
return r;
}
public List<Integer> inorderTraversal_foreach(TreeNode root) {
List<Integer> r = new ArrayList<>();
if (root == null){
return r;
}
//首先创建栈，用于模拟递归入栈出栈的过程
Stack<StackFrame> stack = new Stack<>();
TreeNode p = root;
//将最小树不停的循环
while (true){
//将该元素入栈，一路向左
while (p != null){
//先入栈，再打印
stack.push(new StackFrame(p, 1));
p = p.left;
}
// 再次回来时，状态要变成2，
// 但是同一个结点，有三次为栈顶元素，只有当前元素的状态为1，才可以变成2，状态为3时，不可以修改为2
if (stack.peek().state == 1){
stack.peek().state = 2;
r.add(stack.peek().node.val);
//开始遍历右侧
p = stack.peek().node.right;
continue;
}
//右侧遍历结束
if (stack.peek().state == 2){
stack.peek().state = 3;
stack.pop();
if (stack.isEmpty()){
break;
}
}
}
return r;
}
public List<Integer> inorderTraversal_foreach2(TreeNode root) {
List<Integer> r = new ArrayList<>();
Stack<StackFrame> stack = new Stack<>();
TreeNode p = root;
while (true){
while (p != null){
stack.push(new StackFrame(p, 1));
p = p.left;
}
//第三次回来时，状态由2->3，并且弹出栈
while (!stack.isEmpty() && stack.peek().state == 2){
stack.peek().state = 3;
stack.pop();
}
if (stack.isEmpty()){
break;
}
stack.peek().state = 2;
r.add(stack.peek().node.val);
p = stack.peek().node.right;
}
return r;
}
public static void main(String[] args) {
new Solution5_2().test();
}
public void test(){
TreeNode root = new TreeNode(1);
TreeNode rootr = new TreeNode(2);
TreeNode rootrl = new TreeNode(3);
root.right = rootr;
rootr.left = rootrl;
List<Integer> list = preorderTraversal_foreach(root);
System.out.println(list);
}
}
|