二叉树遍历
二叉树主要有两种遍历方式：
深度优先遍历：先往深走，遇到叶子节点再往回走。深度优先遍历又分：
- 前序遍历（中、左、右）
- 中序遍历（左、中、右）
- 后序遍历（左、右、中）
广度优先遍历：一层一层的去遍历。（后面讲）
递归遍历
递归三要素
- 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
- 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
- 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
List<Integer> res = new ArrayList<>();
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
res.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
public List<Integer> inOrder(TreeNode root, List<Integer> list) {
if (root == null) {
return list;
}
inOrder(root.left, list);
list.add(root.val);
inOrder(root.right, list);
return list;
}
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
res.add(root.val);
}
迭代遍历
二叉树遍历的迭代法，可以使用栈来模拟深度遍历DFS，使用队列来模拟广度遍历BFS!
注意：使用双端队列模拟栈时，如果使用了addLast压栈，对应的就该使用pollLast出栈（推荐使用addLast，因为栈后进先出，压栈操作就是从后面压入的），使用了addFirst压栈，对应使用pollFirst出栈。模拟队列时，addLast对应pollFirst（推荐，队尾入队，队头出队），addFirst对应pollLast。
前序遍历
List<Integer> res = new ArrayList<>();
/**
* 迭代遍历的方法
* 1.创建一个空栈，将根节点压入栈中。
* 2.循环执行以下步骤直到栈为空：
* 2.1弹出栈顶节点，访问该节点。
* 2.2将右子节点（如果存在）压入栈。
* 2.3将左子节点（如果存在）压入栈。注意要先压入右子节点，再压入左子节点，这样在弹出时左子节点会先被处理。
*/
public void preOrder(TreeNode root) {
//1.root为null,不为null则加入根节点
if (root == null) {
return;
}
Deque<TreeNode> stack = new LinkedList<>();
stack.addLast(root);
//2.使用栈,中右左入栈,中左右出栈(为啥不是右左中入栈?因为先访问根节点,才有后面根节点下的左右节点)
while (!stack.isEmpty()) {
//记录栈顶节点,后续要访问它的左右子节点
TreeNode node = stack.peekLast();
//弹出栈顶节点
stack.pollLast();
//记录栈顶节点值
res.add(node.val);
//右孩子入栈
if (node.right != null) {
stack.addLast(node.right);
}
//左孩子入栈
if (node.left != null) {
stack.addLast(node.left);
}
}
}
中序遍历
/**
* 中序遍历迭代法
* 1.初始化栈，将当前节点指向根节点。
* 2进入循环，循环条件是当前节点不为空或者栈不为空。
* 2.1在循环中，首先将当前节点以及其所有左子节点依次入栈，直到最左下角的节点（即最左边的叶子节点）。
* 2.2弹出栈顶节点，访问该节点。
* 2.3将当前节点指向弹出节点的右子节点。(如果右子节点为空,这时当前节点就会变成上一层节点的父节点，然后继续弹出上一层节点并访问它的右子节点)
* 2.4重复上述三个步骤，直到栈为空且当前节点为空。
*/
public List<Integer> inorderTraversal2(TreeNode root) {
// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
/**
* 5
* 4 6
* 1 2
*/
Deque<TreeNode> deque = new ArrayDeque<>();
List<Integer> result = new ArrayList<>();
TreeNode cur = root;
if (root == null) {
return result;
}
while (cur != null || !deque.isEmpty()) {
if (cur != null) {
//一直往下遍历二叉树左节点
deque.addLast(cur);
cur = cur.left;
} else {
//遍历到1的左子结点为null,出栈1
cur = deque.pollLast();
result.add(cur.val);//因为一旦没有左孩子,此时的节点就是中节点,就需要进行处理,接着遍历右孩子
//指针指向1的右子节点,如果也为空继续出栈4
cur = cur.right;//因为右孩子也为空,说明左中右都访问了,需要向上访问父节点了(对应出栈操作)
}
}
return result;
}
后续遍历
/**
* 1.初始化一个ArrayDeque（双端队列）和一个List（用于存储遍历结果）。
* 2.如果根节点不为空，将根节点加入到队列中。
* 3.进入循环，循环条件是队列不为空。
* 从队列的尾部取出一个节点，将节点的值加入到结果列表中。
* 如果节点的左子节点不为空，将左子节点加入队列尾部。
* 如果节点的右子节点不为空，将右子节点加入队列尾部。
* 4.循环结束后，对结果列表进行翻转（因为是后序遍历，所以要翻转结果）。
* 5.返回翻转后的结果列表。
*/
public List<Integer> postorderTraversal2(TreeNode root) {
// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
deque.addLast(root);
while (!deque.isEmpty()) {
TreeNode node = deque.pollLast();
res.add(node.val);
if (node.left != null) {
deque.addLast(node.left);
}
if (node.right != null) {
deque.addLast(node.right);
}
}
Collections.reverse(res);
return res;
}
统一迭代
针对三种遍历方式，使用迭代法是可以写出统一风格的代码！
前序遍历（中左右）
//前序遍历,中左右，入栈顺序右左中
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<>();
//在Java的ArrayDeque中，不允许添加null元素!!!!!!
Deque<TreeNode> deque = new LinkedList<>();
if (root != null) {
deque.addLast(root);//加入结点5
}
while (!deque.isEmpty()) {
TreeNode node = deque.peekLast();//记录结点5 //记录结点4
if (node != null) {
deque.pollLast();//弹出结点5 //弹出结点4
if (node.right != null) {
deque.addLast(node.right);//加入5的右孩子6 //加入4结点的右孩子2
}
if (node.left != null) {
deque.addLast(node.left);//加入5的左孩子4 //加入4结点的左孩子1
}
deque.addLast(node);//加入结点5 (可以发现此时结点入栈顺序是右->左->中,出栈就是中左右) //加入结点4
deque.addLast(null);//加入空节点 //加入空节点
} else {
deque.pollLast();//遇到null就出栈空结点 //遇到null就出栈空节点
node = deque.pollLast();//此时栈顶结点是5,结点5出栈 //此时栈顶是4,结点4出栈
result.add(node.val);//记录5 //记录4 .....
}
}
return result;
}
中序遍历（左中右）
//中序遍历:左中右
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if (root != null) {
deque.addLast(root);
}
while (!deque.isEmpty()) {
TreeNode node = deque.peekLast();
if (node != null) {
// 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
deque.pollLast();
// 添加右节点（空节点不入栈）
if (node.right != null) {
deque.addLast(node.right);
}
// 添加中节点
deque.addLast(node);
// 中节点访问过，但是还没有处理，加入空节点做为标记.
deque.addLast(null);
// 添加左节点（空节点不入栈）
if (node.left != null) {
deque.addLast(node.left);
}
} else {
// 只有遇到空节点的时候，才将下一个节点放进结果集
// 将空节点弹出
deque.pollLast();
// 重新取出栈中元素
node = deque.pollLast();
// 加入到结果集
result.add(node.val);
}
}
return result;
}
后序遍历（左右中）
//后序遍历:左右中
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if (root != null) {
deque.addLast(root);
}
while (!deque.isEmpty()) {
TreeNode node = deque.peekLast();
if (node != null) {
deque.pollLast();
deque.addLast(node);
deque.addLast(null);
if (node.right != null) {
deque.addLast(node.right);
}
if (node.left != null) {
deque.addLast(node.left);
}
} else {
deque.pollLast();
node = deque.peekLast();
deque.pollLast();
result.add(node.val);
}
}
return result;
}
