给定一个二叉树，返回它的 前序 遍历。示例：
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3]从根节点开始，每次迭代弹出当前栈顶元素，并将其孩子节点压入栈中，先压右孩子再压左孩子。
出栈的同时①右孩子入栈②左孩子入栈
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Deque<TreeNode> stack = new LinkedList<>(); if (root != null) { stack.push(root); } while (!stack.isEmpty()) { TreeNode curr = stack.pop(); list.add(curr.val); if (curr.right != null) stack.push(curr.right); if (curr.left != null) stack.push(curr.left); } return list; } }给定一个二叉树，返回它的中序 遍历。示例：
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2]所谓中序遍历，就是先访问其左孩子，然后再访问本节点，最后访问右孩子，可以用动画演示：
入栈：当节点存在左孩子时就**将其入栈并将其左孩子入栈，然后将左边的一条线一直到没有左孩子的节点都入栈**。
出栈：出栈的同时将节点的右孩子入栈，右孩子入栈的时候同上面的入栈规则。
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Deque<TreeNode> stack = new LinkedList<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); list.add(curr.val); curr = curr.right; } return list; } }给定一个二叉树，返回它的 后序 遍历。示例：
输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1]前序遍历的过程 是 中-左-右。将其转化成 中-右-左。也就是压栈的过程中优先压入左子树，再压入右子树。然后将这个结果返回来，就是 左-右-中， 即为后序遍历。
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Deque<TreeNode> stack = new LinkedList<>(); Deque<TreeNode> reverseStack = new LinkedList<>(); if (root != null) { stack.push(root); } while (!stack.isEmpty()) { TreeNode curr = stack.pop(); reverseStack.push(curr); if (curr.left != null) stack.push(curr.left); if (curr.right != null) stack.push(curr.right); } while (!reverseStack.isEmpty()) list.add(reverseStack.pop().val); return list; } }首先三种遍历的递归方法无需多想，递归嘛，只需要考虑一个节点的情况该如何处理，其他的交给计算机去递归就好了，一定不要人肉递归，计算机都会溢出，在意多了细节脑子也会坏掉的。
而至于三种遍历的循环方法，事实上就是在模拟递归，在递归方法中是使用了系统栈，而在循环方法中使用的是我们自己开辟的数据结构栈，所以深度遍历都是通过栈来完成的：
对于前序遍历，其顺序为 中-左-右， 所以我们在遍历过程时，应该先打印左子树，然后打印右子树，这样很自然的就应该理解在栈中我们先压的是右子树，然后压左子树。
对于中序遍历，其顺序为 左-中-右， 其实仔细想想其压栈的规则，是先把根节点的左孩子一趟线都压栈， 但是之后再压入每个右孩子的同时，都将右孩子的左孩子一趟线都压入了栈中，所以出栈时仍是先打印左子树，后打印右子树。
对于后序遍历，其顺序为 左-右-中，观察其顺序和前序遍历的区别，我们可以将后序遍历反其道而行之，与后续遍历恰为相反的遍历为 中-右-左， 而 中-右-左 又该如何遍历呢，这显然在遍历过程时，应该先打印右子树，然后打印左子树，这不就和前序遍历的方式一模一样了嘛，只不过在栈中我们先压的是左子树，然后压右子树，然后我们将得到的遍历顺序取反，就是后序遍历了。
