递归的实现就是:每一次递归调用都会把函数的局部变量，参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，这就是递归为什么可以返回上一层位置的原因

可以用栈实现二叉树的前中后序遍历

1. 前序遍历

先将根节点放入栈中，再将右节点放入栈中，再将左节点放入栈中。栈中只要有元素就循环迭代，无元素则遍历完成

前序遍历的过程中，前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，要访问的元素和要处理的元素是一致的。

List<Integer> list = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if (root == null) return list;
deque.add(root);
while (!deque.isEmpty()){TreeNode node = deque.pop(); //访问list.add(node.val);   //处理//入栈if (node.right != null){deque.push(node.right);}if (node.left != null){deque.push(node.left);}
}return list;

2. 中序遍历

中序遍历，先访问是的二叉树顶部的节点，然后一层一层往下访问，直到到达数左面的最底部，再开始处理节点（也就是将节点数组放入list数组中），这就造成了处理顺序和访问顺序的不一样。

借助指针的遍历来帮助访问节点，栈则用来处理节点上的元素

3. 后序遍历

只要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后再反转list数组，输出的结果就是左右中了。

 public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null){return list;}Deque<TreeNode> deque = new LinkedList<>();deque.add(root);while (!deque.isEmpty()){TreeNode node = deque.pop();list.add(node.val);if (node.left != null)  deque.push(node.left);if (node.right != null) deque.push(node.right);}//倒序 注意i =号List<Integer> res = new ArrayList<>();for (int i = list.size() - 1; i >= 0 ; i--) {res.add(list.get(i));}return res;}