import java.util.ArrayList;

import java.util.List;

import java.util.Stack;

public class InorderTraversal_94 {

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode() {

}

TreeNode(int val) {

this.val = val;

}

TreeNode(int val, TreeNode left, TreeNode right) {

this.val = val;

this.left = left;

this.right = right;

}

}

/**

* 递归解法（比较简单）

* @param root

* @return

*/

public List<Integer> inorderTraversal1(TreeNode root) {

List<Integer> list = new ArrayList<>();

if (root != null) {

list.addAll(inorderTraversal1(root.left));

list.add(root.val);

list.addAll(inorderTraversal1(root.right));

}

return list;

}

/**

* 迭代解法：不断往左边走，当走不下去，就打印节点，并转向右边并继续这个过程

* @param root

* @return

*/

public List<Integer> inorderTraversal2(TreeNode root) {

List<Integer> list = new ArrayList<>();

// 创建栈来模拟递归的调用

Stack<TreeNode> stack = new Stack<>();

while(root != null || stack.size() > 0) {

// 不断往左子树方向走，每走一次就将当前节点保存到栈中

if (root != null) {

stack.add(root);

root = root.left;

} else {

// 当前节点为空说明向左走到头了，此时从栈中拿出元素添加至结果集，并转向右节点继续这个过程

TreeNode temp = stack.pop();

list.add(temp.val);

root = temp.right;

}

}

return list;

}

}