1.前序遍历 根左右

使用栈，因为栈是后入先出，所以使用栈来记录结点，先押入跟结点，在押入右结点和左节点，按照出栈顺序访问元素

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		if (root == null)
			return result;
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()){
			TreeNode temp = stack.pop();
			//left后入栈会先出栈，因为是根左右
			result.add(temp.val);
			if (temp.right != null)
				stack.push(temp.right);
			if (temp.left != null)
				stack.push(temp.left);
		}
		return result;
    }
}

2.后序遍历 左右根

与前序遍历基本一致

• 后序遍历顺序 左-右-中
• 入栈顺序：中-左-右
• 出栈顺序：中-右-左
• 最后翻转结果（一定要记得翻转结果，否则得到的是根右左）

class Solution {
	public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		if (root == null)
			return result;
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()){
			TreeNode temp = stack.pop();
			result.add(temp.val);
			if (temp.left != null){
				stack.push(temp.left);
			}
			if (temp.right != null){
				stack.push(temp.right);
			}
		}
		Collections.reverse(result);
		return result;
	}
}

3. 中序遍历 左根右

单独的思路，因为不能先将根压入栈，那么如果先将left入栈会导致指针的丢失，所以要先找到左子树为空的，也就是下一个元素就是当前的栈顶，即当前子树的根结点

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		if (root == null)
			return result;
		TreeNode cur = root;
		Stack<TreeNode> stack = new Stack<>();
		while (!stack.isEmpty() || cur != null){
			if (cur != null){//此时要找到左子树的底部
				stack.push(cur);
				cur = cur.left;
			}else {//当前结点没有了左子树，那么当前没有左子树的跟结点就是栈顶
				cur = stack.pop();
				result.add(cur.val);
				cur = cur.right;
			}
		}
		return result;
    }
}