1.

思路：

首先创建一个栈和顺序表，按照根左右的前序遍历顺序去遍历这棵树，一直往左孩子方向遍历，每遍历到一个结点就入栈并且加入到顺序表里，如果没有左孩子了，就拿出栈顶元素，看它是否有右孩子，如果有，又从右孩子开始，往左孩子方向遍历，如果没有，就继续拿出栈顶元素，如此循环，直到栈为空

class Solution {Stack<TreeNode> stack=new Stack<>();List<Integer> list=new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {if(root==null){//如果为空树return list;}TreeNode cur=root;//cur用来以前序遍历顺序来遍历树while(cur!=null||!stack.isEmpty()){//如果此时有遍历到结点，或者栈不为空while(cur!=null){//如果是此时有遍历到结点stack.push(cur);list.add(cur.val);cur=cur.left;}//此时没有遍历到结点TreeNode top=stack.pop();//拿出栈顶元素if(top.right!=null){//如果有右孩子cur=top.right;//遍历右孩子}}return list;}
}

2.

思路：

同上题一样，只不过由根左右变成左根右，所以往顺序表里面添加元素的地方要继续调整

class Solution {List<Integer> list=new ArrayList<>();Stack<TreeNode> stack=new Stack<>();public List<Integer> inorderTraversal(TreeNode root) {if(root==null){return list;}TreeNode cur=root;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}TreeNode top=stack.pop();list.add(top.val);//说明没有左孩子，到了左根右的根，打印if(top.right!=null){cur=top.right;}}return list;}
}

3.

思路：

因为后序遍历是左右根，所以先遍历到的是根，但最后输出的才是根，贴合栈这种“先进后出”的数据结构，所以要采用到栈这个数据结构

根据左右根的顺序，先一直让左孩子结点全部入栈，如果左孩子为null，则看看现在栈顶元素是否有右孩子，没有就出栈，有就将右孩子入栈，再次循环

但是这里有可能出现死循环，就是下图这种情况

当遍历到A，左孩子为null，此时A为栈顶元素，A有右孩子B，所以B入栈，然后B没有左右孩子，所以B出栈，此时A没有左孩子，A为栈顶元素，A有右孩子B，B又入栈，然后B没有左右孩子，B又出栈……

所以我们还有添加一种判断情况，即已经入栈再出栈了的我们不再入栈，所以要创建一个结点来记录入栈再出栈了的这种结点，如果是B这种结点，则栈顶元素A继续出栈而不是让B这种结点再入栈

class Solution {public List<Integer> postorderTraversal(TreeNode root) {//记录后序遍历的数组List<Integer> list=new ArrayList<>();//如果为空结点，直接返回空数组if(root==null){return list;}Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;TreeNode prev=null;//用来记录已经入栈又出栈了的结点//如果结点不为空，或者栈不为空while(cur!=null||!stack.isEmpty()){//将左孩子全部入栈或者没有左孩子但是有右孩子的while(cur!=null){stack.push(cur);cur=cur.left;}//此时cur为null，看看栈顶元素TreeNode top=stack.peek();//如果栈顶元素也没有右孩子，或者右边已经入栈又出栈了的if(top.right==null||top.right==prev){//将栈顶元素输出并出栈list.add(top.val);stack.pop();//记录当前结点为入栈又出栈了的prev=top;}else{//有右孩子且不是入栈又出栈了的cur=top.right;}}return list;}
}