【算法总结】递归和非递归实现二叉树的先序，中序，后序遍历 (2)

前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。

//修改前序遍历代码中，节点写入结果链表的代码：将插入队尾修改为插入队首 //修改前序遍历代码中，每次先查看左节点再查看右节点的逻辑：变为先查看右节点再查看左节点 class Solution {     public List<Integer> postorderTraversal(TreeNode root) {         LinkedList res = new LinkedList();         Stack<TreeNode> stack = new Stack<>();         TreeNode pre = null;         while(root!=null || !stack.empty()){             while(root!=null){                 res.addFirst(root.val); //插入队首                 stack.push(root);                 root = root.right; //先右后左             }             root = stack.pop();             root = root.left;         }         return res;      } } 复制代码 非递归实现二叉树的层序遍历

leetcode：leetcode.com/problems/bi…

class Solution {     public List<List<Integer>> levelOrderBottom(TreeNode root) {         List<List<Integer>> res = new LinkedList<>();         Queue<TreeNode> queue = new LinkedList<>();         if(root == null)             return res;         queue.add(root);         while(!queue.isEmpty()){             int count = queue.size();             List<Integer> temp = new LinkedList<>();             for(int i=0; i<count; i++){                 TreeNode node = queue.poll();                 temp.add(node.val);                 if(node.left != null)                     queue.add(node.left);                 if(node.right != null)                     queue.add(node.right);             }             // 每次都添加到第一个位置             res.add(0, temp);         }         return res;     } } 复制代码 小结

递归实现二叉树的前中后遍历，这种方式非常简单，大家一定要掌握