二叉树迭代遍历（三种写法）

写法一（各个步骤分离）

前序遍历

	class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();//迭代算法preorderStack(root, list);return list;}  //通过栈的先进后出特性，将root节点放到栈中，对二叉树从遍历	   public void preorderStack(TreeNode root, List<Integer> list){Deque<TreeNode> stack = new LinkedList<>();        while(root != null || stack.isEmpty()){//root不为null时，将root节点和左子树节点放到栈中while(root != null){//获取根节点数据list.add(root.val);//将root节点放入栈中stack.push(root);//处理root左子树节点root = root.left;}//root为null，获取栈中root节点root = stack.pop();//处理root右子树节点root = root.right;}}}

中序遍历

	class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();//迭代算法inorderStack(root, list);return list;}  //通过栈的先进后出特性，将root节点放到栈中，对二叉树从遍历	   public void inorderStack(TreeNode root, List<Integer> list){//定义一个栈用于存放二叉树Deque<TreeNode> stack = new LinkedList<>();        while(root != null || stack.isEmpty()){//root不为null时，将root节点和左子树节点放到栈中while(root != null){                    //将root节点放入栈中stack.push(root);//处理root左子树节点root = root.left;}//root为null，获取栈中root节点root = stack.pop();//获取根节点数据list.add(root.val);//处理root右子树节点root = root.right;}}}

后序遍历

	class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();//迭代算法postorderStack(root, list);return list;}  //通过栈的先进后出特性，将root节点放到栈中，对二叉树从遍历	   public void postorderStack(TreeNode root, List<Integer> list){//定义一个栈用于存放二叉树Deque<TreeNode> stack = new LinkedList<>(); //用于判断当前处理右子树与上次处理的二叉树是否相同，避免再处理一次TreeNode pre = null;       while(root != null || stack.isEmpty()){//root不为null时，将root节点和左子树节点放到栈中while(root != null){                    //将root节点放入栈中stack.push(root);//处理root左子树节点root = root.left;}//root为null，获取栈中root节点root = stack.pop();//右子树为null 或 右子树 与 上次处理的pre 子树相等 不需在处理一遍， 取root节点值if(root.right == null || root.right == pre){                    //获取根节点数据list.add(root.val);//将当前root节点赋值给pre 用于标记pre = root;//将root重置为null，再次出栈遍历处理root = null;}else{//右子树不为null时，需将右子树入栈处理stack.push(root);//处理root右子树节点root = root.right;}                }}}

写法二

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
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 node = stack.pop();result.add(node.val);if (node.right != null){stack.push(node.right);}if (node.left != null){stack.push(node.left);}}return result;}
}// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
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 node = stack.pop();result.add(node.val);if (node.left != null){stack.push(node.left);}if (node.right != null){stack.push(node.right);}}Collections.reverse(result);return result;}
}

写法三（三种遍历统一格式）

迭代法前序遍历代码如下:class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右左中节点添加到栈中（前序遍历-中左右，入栈顺序右左中）if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）st.push(node);                          // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}
}
迭代法中序遍历代码如下:class Solution {
public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中（中序遍历-左中右，入栈顺序右中左）if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）st.push(node);                          // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;
}
}
迭代法后序遍历代码如下:class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将中右左节点添加到栈中（后序遍历-左右中，入栈顺序中右左）st.push(node);                          // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         } else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}
}