典中典之二叉树遍历。
常用的BFS和DFS对树的遍历，是很多题目的解题通用模板。掌握这两种方法遍历二叉树尤其重要！！！
在这里进行整理。
DFS（深度优先算法）遍历二叉树
以前序遍历为例子。
DFS遍历二叉树的主要实现思路就是使用栈来保存父节点，并依次遍历左右子树。
下文主要以迭代法和递归法两种方式来描述。
迭代法（从顶向下）
迭代法比较好理解。
思路
维护一个数组和一个栈。
其中：
数组用来保存每次遍历走过的路径。
栈用来保存每次遍历的结点的父节点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> path=new ArrayList<>();
if(root==null){return path;}
Stack<TreeNode> s=new Stack<>();
s.push(root);
while(!s.isEmpty()){
TreeNode curNode=s.pop();
path.add(curNode.val);
if(curNode.right!=null) s.push(curNode.right);
if(curNode.left!=null) s.push(curNode.left);
}
return path;
}
}
|
递归法
递归法，实际上是利用递归栈的特性来实现的dfs遍历。
递归法虽然理解起来稍微复杂，但直观简洁，一看基本上就能记得住，适合用来当代码模板。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
preorder(root, res);
return res;
}
public void preorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
preorder(root.left, res);
preorder(root.right, res);
}
}
|
BFS（广度优先算法）层序遍历二叉树
层序遍历的模板我个人觉得是比较容易接受的。
思路
维护一个数组和一个队列。
其中：
数组用来保存每次遍历走过的路径。
队列用来保存每次遍历的结点的左右子树。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int[] levelOrder(TreeNode root) {
if(root==null) return new int[0];
Queue<TreeNode> q=new LinkedList<>();
q.add(root);
List<Integer> res=new ArrayList<>();
while(!q.isEmpty()){
TreeNode cur=q.poll();
res.add(cur.val);
if(cur.left!=null){
q.add(cur.left);
}
if(cur.right!=null){
q.add(cur.right);
}
}
int[] resArray=new int[res.size()];
for(int i=0;i<res.size();i++){
resArray[i]=res.get(i);
}
return resArray;
}
|