一篇文章教你如何用多种迭代写法实现二叉树遍历

思想

利用栈和队列都可以实现树的迭代遍历。递归的写法将这个遍历的过程交给系统的堆栈去实现了，所以思想都是一样的、无非就是插入值的时机不一样。利用栈的先进先出的特点，对于前序遍历、我们可以先将当前的值放进结果集中，表示的是根节点的值、然后将当前的节点加入到栈中、当前的节点等于自己的left、再次循环的时候、也会将left作为新的节点、直到节点为空、也就是走到了树的最左边、然后回退、也就是弹栈、、也可以认为回退的过程是从低向上的、具体就是让当前的节点等于栈弹出的right、继续重复上面的过程，也就实现了树的前序遍历、也就是bfs.后续遍历、中序遍历思想也是类似的。

实现

   public List<Integer> preorderTraversal1(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       Stack<TreeNode> stack = new Stack<>();
       while (!stack.isEmpty() || root != null) {
           while (root != null) {
               res.add(root.val);
               stack.add(root);
               root = root.left;
           }
           TreeNode cur = stack.pop();
           root = cur.right;
       }
       return res;
   }
   public List<Integer> preorderTraversal2(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       Stack<TreeNode> stack = new Stack<>();
       while (!stack.isEmpty() || root != null) {
           if (root != null) {
               res.add(root.val);
               stack.add(root);
               root = root.left;
           } else {
               TreeNode cur = stack.pop();
               root = cur.right;
           }
       }
       return res;
   }
   public List<Integer> preorderTraversal3(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       if (root == null) return res;
       Stack<TreeNode> stack = new Stack<>();
       stack.push(root);
       while (!stack.isEmpty()) {
           TreeNode cur = stack.pop();
           res.add(cur.val);
           if (cur.right != null) {
               stack.push(cur.right);
           }
           if (cur.left != null) {
               stack.push(cur.left);
           }
       }
       return res;
   }
   public List<Integer> preorderTraversal4(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       if (root == null) {
           return res;
       }
       LinkedList<TreeNode> queue = new LinkedList<>();
       queue.add(root);
       while (!queue.isEmpty()) {
           root = queue.poll();
           res.add(root.val);
           if (root.right != null) {
               queue.addFirst(root.right);
           }
           if (root.left != null) {
               root = root.left;
               while (root != null) {
                   res.add(root.val);
                   if (root.right != null) {
                       queue.addFirst(root.right);
                   }
                   root = root.left;
               }
           }
       }
       return res;
   }
   public List<Integer> inorderTraversal1(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       Stack<TreeNode> stack = new Stack<>();
       while (root != null || !stack.isEmpty()) {
           if (root != null) {
               stack.add(root);
               root = root.left;
           } else {
               TreeNode cur = stack.pop();
               res.add(cur.val);
               root = cur.right;
           }
       }
       return res;
   }
   public List<Integer> inorderTraversal2(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       Stack<TreeNode> stack = new Stack<>();
       while (root != null || !stack.isEmpty()) {
           while (root != null) {
               stack.add(root);
               root = root.left;
           }
           TreeNode cur = stack.pop();
           res.add(cur.val);
           root = cur.right;
       }
       return res;
   }
   public List<Integer> postorderTraversal1(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       if (root == null) return res;
       Stack<TreeNode> stack = new Stack<>();
       stack.push(root);
       while (!stack.isEmpty()) {
           TreeNode cur = stack.pop();
           res.add(cur.val);
           if (cur.left != null) {
               stack.push(cur.left);
           }
           if (cur.right != null) {
               stack.push(cur.right);
           }
       }
       Collections.reverse(res);
       return res;
   }
   public List<Integer> postorderTraversal2(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       Stack<TreeNode> stack = new Stack<>();
       while (!stack.isEmpty()) {
           while (root != null) {
               res.add(root.val);
               stack.push(root);
               root = root.right;
           }
           TreeNode cur = stack.pop();
           root = cur.left;
       }
       Collections.reverse(res);
       return res;
   }
   public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> ret = new ArrayList<>();
       if(root == null)return ret;
       Queue<TreeNode> queue = new LinkedList<>();
       queue.offer(root);
       while (!queue.isEmpty()){
           int size = queue.size();
           List<Integer> list = new ArrayList<>();
           while(size!=0){
               TreeNode cur = queue.poll();
               list.add(cur.val);
               if(cur.left!=null){
                   queue.offer(cur.left);
               }
               if(cur.right!= null){
                   queue.offer(cur.right);
               }
               size --;
           }
           ret.add(list);
       }
       return ret;
   }

来源：https://blog.csdn.net/qq_45859087/article/details/119141358