我的 CSDN 博客:blog.csdn.net/gdutxiaoxu
我的掘金：juejin.im/user/220747…
github: github.com/gdutxiaoxu/
微信公众号：程序员徐公
说到树的四种遍历方式，可能大家第一时间都会想到它的四种遍历方式，并快速说了它的特点。
先序(先根)遍历：即先访问根节点，再访问左孩子和右孩子
中序遍历：先访问做孩子，再访问根节点和右孩子
后序遍历：先访问左孩子，再访问右孩子，再访问根节点
层次遍历：按照所在层数，从下往上遍历
接着当你要手动写代码的时候，你写得出来嘛？
递归实现二叉树的前序，中序，后续遍历
非递归二叉树的实现前序，中序，后续遍历
实现二叉树的层序遍历
今天，就让我们一起来看看，怎样实现它？
前中后序遍历假如有以下树
1 / \ 2 3 / \ \ 4 5 6 复制代码它的前中后续遍历分别如下
层次遍历顺序：[1 2 3 4 5 6]
前序遍历顺序：[1 2 4 5 3 6]
中序遍历顺序：[4 2 5 1 3 6]
后序遍历顺序：[4 5 2 6 3 1]
层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性；而前序、中序、后序遍历利用了 DFS 实现。
前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。
递归实现前序，中序，后序遍历① 前序
void dfs(TreeNode root) { visit(root); dfs(root.left); dfs(root.right); } 复制代码② 中序
void dfs(TreeNode root) { dfs(root.left); visit(root); dfs(root.right); 复制代码③ 后序
void dfs(TreeNode root) { dfs(root.left); dfs(root.right); visit(root); } 复制代码 非递归实现二叉树的先序，中序，后序遍历 非递归实现二叉树的前序遍历144. Binary Tree Preorder Traversal (Medium)
Leetcode / 力扣：leetcode-cn.com/problems/bi…
class Solution { //迭代 public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); while(root!=null || !stack.empty()){ while(root!=null){ res.add(root.val); //先将节点加入结果队列 stack.push(root); //不断将该节点左子树入栈 root = root.left; } root = stack.pop(); //栈顶节点出栈 root = root.right; //转向该节点右子树的左子树（下一个循环） } return res; } } 复制代码 非递归实现二叉树的中序遍历94. Binary Tree Inorder Traversal (Medium)
Leetcode / 力扣：leetcode-cn.com/problems/bi…
class Solution { //迭代 public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); while(root!=null || !stack.empty()){ while(root!=null){ stack.push(root); //不断将该节点左子树入栈 root = root.left; } root = stack.pop(); //栈顶节点出栈 res.add(root.val); //将节点加入结果队列 root = root.right; //转向该节点右子树的左子树（下一个循环） } return res; } } 复制代码 非递归实现二叉树的后序遍历145. Binary Tree Postorder Traversal (Medium)
Leetcode / 力扣：leetcode-cn.com/problems/bi…