一文弄懂二叉树三种遍历（一文搞懂二叉树的遍历算法）

代码：

/** * @desc: 二叉树的数据结构 * @author: YanMingXin * @create: 2021/9/24-10:46 **/ public class TreeNode<E> { public E val; public TreeNode<E> leftNode; public TreeNode<E> rightNode; public TreeNode(E val) { this.val = val; } public TreeNode(E val, TreeNode<E> leftNode, TreeNode<E> rightNode) { this.val = val; this.leftNode = leftNode; this.rightNode = rightNode; } }

（1）概念

“根—左—右”，顾名思义就是先根节点，再左子树，最后是右子树

（2）图解

（3）代码实现

递归方式：

/** * 辅助列表 */ private ArrayList<Object> list = new ArrayList<>(); /** * 前序遍历（递归方式） * * @param tree * @return */ public List prePrint(TreeNode tree) { if (tree == null) { return list; } list.add(tree.val); prePrint(tree.leftNode); prePrint(tree.rightNode); return list; }

非递归方式：

/** * 辅助列表 */ private ArrayList<Object> list = new ArrayList<>(); /** * 辅助栈 */ private Stack<TreeNode> stack = new Stack<>(); /** * 前序遍历（非递归） * * @param treeNode * @return */ public List prePrint2(TreeNode treeNode) { //获取根节点 TreeNode root = treeNode; //如果根节点不为空或栈不为空则进行循环 while (root != null || !stack.isEmpty()) { if (root != null) { //压入元素 stack.push(root); //获取值 list.add(root.val); //指向左节点 root = root.leftNode; } else { //弹出元素 root = stack.pop(); //指向右节点 root = root.rightNode; } } return list; }

（1）概念

“左—右—根”，顾名思义就是先左子树，再右子树，最后是根节点

（2）图解

（3）代码实现

递归实现：

/** * 辅助列表 */ private ArrayList<Object> list = new ArrayList<>(); /** * 后序遍历（递归方式） * * @param tree * @return */ public List afterPrint(TreeNode tree) { if (tree == null) { return list; } afterPrint(tree.leftNode); afterPrint(tree.rightNode); list.add(tree.val); return list; }

非递归实现：

/** * 辅助列表 */ private ArrayList<Object> list = new ArrayList<>(); /** * 辅助栈 */ private Stack<TreeNode> stack = new Stack<>(); /** * 后序遍历（非递归） * * @param treeNode * @return */ public List afterPrint2(TreeNode treeNode) { TreeNode root = treeNode; TreeNode pre = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.leftNode; } root = stack.pop(); if (root.rightNode == null || root.rightNode == pre) { list.add(root.val); pre = root; root = null; } else { stack.push(root); root = root.rightNode; } } return list; }

（1）概念

“左—根—右”，顾名思义就是先左子树，再根节点，最后是右子树

（2）图解

（3）代码实现

递归实现：

/** * 辅助列表 */ private ArrayList<Object> list = new ArrayList<>(); /** * 中序遍历（递归方式） * * @param tree * @return */ public List midPrint(TreeNode tree) { if (tree == null) { return list; } midPrint(tree.leftNode); list.add(tree.val); midPrint(tree.rightNode); return list; }

非递归实现：

/** * 辅助列表 */ private ArrayList<Object> list = new ArrayList<>(); /** * 辅助栈 */ private Stack<TreeNode> stack = new Stack<>(); /** * 中序遍历（非递归） * * @param treeNode * @return */ public List midPrint2(TreeNode treeNode) { TreeNode root = treeNode; while (root != null || !stack.isEmpty()) { if (root != null) { stack.push(root); root = root.leftNode; } else { root = stack.pop(); list.add(root.val); root = root.rightNode; } } return list; }

（1）概念

层次遍历又称广度优先遍历，是从上到下按层次依次进行遍历

（2）图解

（3）代码实现

/** * 辅助列表 */ private ArrayList<Object> list = new ArrayList<>(); /** * 辅助队列 */ private Queue<TreeNode> queue = new LinkedList(); /** * 层次遍历 * * @param tree * @return */ public List levelPrint(TreeNode tree) { if (tree == null) { return new ArrayList(); } queue.add(tree); while (!queue.isEmpty()) { TreeNode obj = queue.poll(); list.add(obj.val); if (obj.leftNode != null) { queue.add(obj.leftNode); } if (obj.rightNode != null) { queue.add(obj.rightNode); } } return list; }