二叉树遍历及递归算法（一文搞懂二叉树的遍历算法）
二叉树遍历及递归算法（一文搞懂二叉树的遍历算法）“左—右—根”，顾名思义就是先左子树，再右子树，最后是根节点/** * 辅助列表 */ 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)
1 二叉树的数据结构
代码：
/**
* @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;
}
}2 遍历算法概览
（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;
}3.2 后序遍历
（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;
}3.3 中序遍历
（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;
}3.4 层次遍历
（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;
}
