一、深度优先遍历二叉树
1.前序遍历
1.1.递归遍历
1.1.1.思路
递归遍历二叉树相对简单:
- 考虑特殊情况：当根节点为空的时候，直接返回null
- 如果根不为空，则将根的值添加进入List
- 判断左右节点是否为空，非空则开始递归
- 递归的方法：用于判断是否还有左右节点，添加节点的值，有节点则继续递归，没有则返回上一个节点
DFS（）参数：node.left，node.right
无返回值，因为List是引用类型，所以不用返回值，直接添加值
1.1.2.代码
点击查看代码
//递归 二叉树的前序遍历
import java.util.LinkedList;
import java.util.List;
class Solution2 {
//定义一个链表用来接收答案
LinkedList<Integer> list = new LinkedList<>();
public List<Integer> preorderTraversal(TreeNode root) {
//考虑特殊情况
if(root==null)return list;
list.add(root.val);
//如果左边不为空就先对左边进行深度优先查询
if (root.left != null) {
DFS(root.left);
}
if (root.right != null) {
DFS(root.right);
}
return list;
}
//1\首先处理传入的值
//2\在进行下一步判断和调用递归
public void DFS(TreeNode node) {
list.add(node.val);
if (node.left!= null) {
DFS(node.left);
}
if (node.right != null) {
DFS(node.right);
}
}
}
1.2.迭代遍历
1.2.1.思路
相对与递归，迭代会更麻烦:
1.
2.
1.2.2.代码
点击查看代码
//不用递归,而是用迭代查询
import java.util.*;
class Solution1 {
//定义一个栈(stack已经过时,而deque是stack的升级版),用来存储节点,目的是可以返回上一个节点
//定义一个链表,用来存储节点的值,最后的答案
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<Integer> list=new LinkedList<>();
//特殊情况
if(root==null)return list;
Deque<TreeNode> stack=new LinkedList<>();
stack.push(root);
TreeNode node=root;
//这里是重点,如果node是空,则将栈中节点推出,返回上一个节点
//如果node非空,则推入栈中方便返回上一个节点,继续向左边遍历
while(!stack.isEmpty()){
while(node!=null){
list.add(node.val);
stack.push(node);
node=node.left;
}
node=stack.pop();
node=node.right;
}
return list;
}
}
2.中序遍历
2.1.递归遍历
2.1.1.思路
与前序遍历的思路一样，但是添加值的位置改变了:
2.1.2.代码
点击查看代码
class Solution3 {
public List<Integer> inorderTraversal(TreeNode root) {
LinkedList<Integer> list = new LinkedList<>();
if (root == null) return list;
if (root.left != null) {
DFS(root.left, list);
}
list.add(root.val);
if (root.right != null) {
DFS(root.right, list);
}
return list;
}
private void DFS(TreeNode node, LinkedList<Integer> list) {
if (node.left != null) {
DFS(node.left, list);
}
list.add(node.val);
if (node.right != null) {
DFS(node.right, list);
}
}
}
3.后序遍历
3.1.递归遍历
3.1.1.思路
与前面的前序遍历和中序遍历相差不大，依然是换了添加值的位置:
3.1.2.代码
点击查看代码
//后续遍历，递归
import java.util.LinkedList;
import java.util.List;
class Solution4 {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> list=new LinkedList<>();
if(root==null)return list;
if(root.left!=null)DFS(root.left,list);
if(root.right!=null)DFS(root.right,list);
list.add(root.val);
return list;
}
private void DFS(TreeNode node,List<Integer> list){
if(node.left!=null)DFS(node.left,list);
if(node.right!=null)DFS(node.right,list);
list.add(node.val);
}
}
二、广度优先遍历二叉树
1.层序遍历
1.1思路
使用广度优先进行遍历:
- 第一步依然是考虑特殊情况
- 创建一个队列和一个链表，队列用于添加节点，链表用来添加答案
- 首先将根节点添加进答案
- 创建一个while循环，只要队列不为空，则不断将节点的值添加进答案中
- 在while里面创建一个for循环，每次遍历poll出树的一层节点，并添加下一层节点（在for前面要提前声明一个size来得到当前层的节点数，第一次遍历在这里卡了好久）
1.2代码
点击查看代码
class Solution2 {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
LinkedList<List<Integer>> answer = new LinkedList<>();
if (root == null) return answer;
queue.add(root);
LinkedList<Integer> rootlist = new LinkedList<Integer>();
rootlist.add(root.val);
answer.add(rootlist);
while (!queue.isEmpty()) {
// LinkedList<Integer> list=new LinkedList<>();
// while(!queue.isEmpty()) {1
// node = queue.poll();
// if (node.left != null) {
// list.add(node.left.val);
// }
// if (node.right != null) {
// list.add(node.right.val);
// }
// queue.add(node.left);
// queue.add(node.right);
// if (!list.isEmpty()) answer.add(list);
//
// }
//遇到的问题：如何让一个list添加一层的节点的值而不是一个节点下面的两个节点的值的值？
LinkedList<Integer> list = new LinkedList<>();
//可以利用queue.size，指定一个size次的for循环，这样poll()出去的节点就是上一层的所有节点
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
list.add(node.left.val);
queue.add(node.left);
}
if (node.right != null) {
list.add(node.right.val);
queue.add(node.right);
}
}
//而list内的值也是当前层的值
if (!list.isEmpty()) answer.add(list);
//一次for之后，queue里面的节点是当前层的节点，因为上一层的size个节点已经被poll()出去了
}
return answer;
}
}
三、文章内容的梳理
相关练习可以在LeetCode上面找到