深度优先搜索
深度优先搜索（Depth First Search），一般用递归实现，算法比较巧妙，关键在于寻找遍历的套路。
前序遍历
递归法
1
2
3
4
5
6
7
8
| public void dfs(TreeNode x) {
if(x == null) {
return;
}
dfs(x.left);
dfs(x.right);
}
|
迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public void dfs(TreeNode x) {
if(x == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(x);
while(!stack.empty()) {
TreeNode node = stack.pop();
if(node.right != null) {
stack.push(node.right);
}
if(node.left != null) {
stack.push(node.left);
}
}
}
|
中序遍历
中序遍历可以按顺序访问二叉搜索树中的节点。
递归法
1
2
3
4
5
6
7
8
| public void dfs(TreeNode x) {
if(x == null) {
return;
}
dfs(x.left);
dfs(x.right);
}
|
迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public void dfs(TreeNode x) {
if(x == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = x;
while(curr != null || !stack.empty()) {
while(curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
curr = curr.right;
}
}
|
后序遍历
递归法
1
2
3
4
5
6
7
8
| public void dfs(TreeNode x) {
if(x == null) {
return;
}
dfs(x.left);
dfs(x.right);
}
|
迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public void dfs(TreeNode x) {
if(x == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> result = new Stack<>();
stack.push(x);
while(!stack.empty()) {
TreeNode node = stack.pop();
result.push(node);
if(node.left != null) {
stack.push(node.letf);
}
if(node.right != null) {
stack.push(node.right);
}
}
while(!result.empty()) {
TreeNode node = result.pop();
}
}
|
广度优先搜索
广度优先搜索（Breadth First Search），即层序遍历，一般用队列加两层循环实现，外层循环遍历树的层次，内循环遍历每一层的节点。
自顶向下层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public void bfs(TreeNode x) {
if(x == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(x);
while(!queue.isEmpty()) {
int count = queue.size();
while(count > 0) {
TreeNode node = queue.poll();
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
count --;
}
}
}
|
自底向上层序遍历
可以用自顶向下遍历法的套路，在具体处理上反转结果。
