经典算法——二叉树遍历问题
2022-05-20 本文已影响0人
_冻茶
姓名：谭旭东
学号：19011210016
一、基本概念
二叉树有一般有三种遍历方法：根据遍历顺序不同而区分
-
前序遍历：根左右（第一次访问节点，直接获取值）
-
中序遍历：左根右（第二次访问节点时，也就是从该节点左子树回来时，获取该节点值）
-
后序遍历：左右根（第三次访问节点时，也就是从该节点右子树回来时，获取该节点值）
-
在遍历过程中，我们访问节点的顺序固定不变：根左右
- 但我们可以调整读取节点值的时间，来达成我们想要的顺序
- 注：二叉树还有层序遍历，一般使用类bfs的队列方法来做
二、前序遍历
1. 递归写法
// 前序：递归方法遍历
public List<Integer> preOrder1(TreeNode root) {
List<Integer> ans = new ArrayList<>();
preOrder_dfs(root, ans);
return ans;
}
public void preOrder_dfs(TreeNode node, List<Integer> ans) {
if (node == null)
return;
// 前序遍历：首次进入节点即获取值
ans.add(node.val);
preOrder_dfs(node.left, ans);
preOrder_dfs(node.right, ans);
}
2. 非递归写法
- 不使用递归的情况下，使用栈来保存各个节点
- 并且调整入栈出栈顺序，达成我们要访问的顺序结果
public List<Integer> preOrder2(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
/*
栈解法：前序遍历，按照根左右的顺序
由于栈是先进后出，需要调整入栈顺序
1.根节点（栈顶节点）直接出栈，加入队列
2.我们要的顺序：先访问左节点（左子树）再访问右节点（右子树）
3.入栈顺序：先加入右节点，再加入左节点
*/
while (!stack.isEmpty()) {
TreeNode curNode = stack.pop();
ans.add(curNode.val);
if (curNode.right != null)
stack.push(curNode.right);
if (curNode.left != null)
stack.push(curNode.left);
}
return ans;
}
三、中序遍历
1. 递归写法
// 中序：递归方法遍历，左根右
public List<Integer> inOrder1(TreeNode root) {
List<Integer> ans = new ArrayList<>();
inOrder_dfs(root, ans);
return ans;
}
public void inOrder_dfs(TreeNode node, List<Integer> ans) {
if (node == null)
return;
// 中序遍历：从左孩子节点返回时，获取节点值
preOrder_dfs(node.left, ans);
ans.add(node.val);
preOrder_dfs(node.right, ans);
}
2. 非递归写法
public List<Integer> inOrder2(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
/*
栈解法：中序遍历，需要按照左根右顺序入队
对每一颗子树，我们都这样做
1.需要先一直往左遍历，直到最左侧最深节点，同时还要记录节点路径
2.最左最深节点可以直接获取值（子树为空，不需访问），然后返回上一层节点（栈中保存记录）
3.上层节点此时可直接获取值（已经从左子树返回，属于第二次访问，该节点为左子树的根）
4.在访问该上层节点的右节点，按照123步骤继续
*/
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
// 左
while (cur != null) { // 先往左走到最深
stack.push(cur); // 记录路径
cur = cur.left;
}
TreeNode node = stack.pop();
ans.add(node.val); // 栈顶元素为该子树最左最深节点，直接获取其值
// 右
if (node.right != null) { // 访问右子树
cur = node.right;
}
}
return ans;
}
四、后序遍历
1. 递归写法
// 后续：递归方法遍历，左右根
public List<Integer> postOrder1(TreeNode root) {
List<Integer> ans = new ArrayList<>();
postOrder_dfs(root, ans);
return ans;
}
public void postOrder_dfs(TreeNode node, List<Integer> ans) {
if (node == null)
return;
// 后续遍历：从右孩子节点返回时，获取节点值
postOrder_dfs(node.left, ans);
postOrder_dfs(node.right, ans);
ans.add(node.val);
}
2. 非递归写法
public List<Integer> postOrder2(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = root; // 指针cur标记当前退出的节点
stack.push(root);
/*
使用栈：后续遍历，要求顺序，左右根
由于节点路径要保留，所以先用peek查看，而不用pop
1.对每一颗子树，我们先一直访问直至其最左最深节点
2.然后获取最左最深节点值，返回上一层
3.在上一层需要进行判断，左子树和右子树是否访问过
我们通过加入节点记录值pre，记录上次退出的节点
(1)如果上次从左子树/右子树退出，表明左子树不需再访问
(2)如果上次从右子树退出，表明右子树不需再访问
4.如果满足条件，继续按照上述123步骤，访问其左子树/右子树
*/
while (!stack.isEmpty()) {
TreeNode peek = stack.peek();
// cur = peek是记录上次退出的节点
// 如果上次退出的节点和左/右子节点相同，则表示那边的子树已经访问过了，不需要再访问
// 左子节点不为空时，需要判断左右节点是否需要再访问
// 右节点不为空时，此时已经从左节点返回，不会再访问左节点，故只需判断右节点是否需要访问
if (peek.left != null && peek.left != pre && peek.right != pre) {
stack.push(peek.left); // 往左遍历
} else if (peek.right != null && peek.right != pre) {
stack.push(peek.right); // 往右遍历
} else {
ans.add(stack.pop().val); // 左右都空
pre = peek;
}
}
return ans;
}
- 后序遍历还有一种方法：
- 将前序遍历左右顺序换一下，变为（根右左）
- 然后得到变形的前序遍历结果，将结果反转可以得到后序遍历（左右根）
- 代码省略，改一下访问顺序即可
五、层序遍历
1. 从上到小层序遍历
// 层序遍历：从上往下
public List<Integer> levelOrder(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
ans.add(cur.val);
if (cur.left != null)
queue.add(cur.left);
if (cur.right != null)
queue.add(cur.right);
}
}
return ans;
}
2. 从下往上遍历
// 层序遍历：从下往上
public List<Integer> levelOrder_desc(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 分层记录
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
temp.add(cur.val);
if (cur.left != null)
queue.add(cur.left);
if (cur.right != null)
queue.add(cur.right);
}
lists.add(new ArrayList<>(temp));
}
List<Integer> ans = new ArrayList<>();
for (int i = lists.size() - 1; i >= 0; i--) {
List<Integer> l = lists.get(i);
ans.addAll(l);
}
return ans;
}
