算法专题:二叉树(BFS/DFS)(先/中/后序遍历)

二叉树


(一)遍历

1.BFS:【队列】

从上往下打印出二叉树的每个节点,同层节点从左至右打印。

思路

BFS(Breadth First Search,广度优先搜索),常用策略是用队列进行遍历。

  1. JDK8Queue<>接口不能直接使用,一般使用它的具体实现类LinkedList进行实例化
  2. Queue.add(E e):入队
  3. Queue.poll():弹出队首
  4. Queue.isEmpty():判空

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {

public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {

ArrayList<Integer> rst = new ArrayList<Integer>();

//Queue是接口,使用它的具体实现类LinkedList
Queue<TreeNode> queue = new LinkedList<TreeNode>();

if (root != null) {
//add(E e) 入队
queue.add(root);
}

//isEmpty() 判空
while (!queue.isEmpty() ) {
//poll() 弹出队首
TreeNode temp = queue.poll();
rst.add(temp.val);

//左右节点可能为空,所以一定要判空
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}

return rst;
}
}

2.DFS:【栈/递归】

输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)

  1. 递归
1
2
3
4
5
dfs(root) {
if(root == null) return;
if(root.left != null) dfs(root.left);
if(root.right != null) dfs(root.right);
}
1
2
3
4
5
6
7
8
9
10
11
dfs(root) {
if(root == null) return;
Stack s;
s.push(root);
while(!s.isEmpty() ) {
//先加入右子树,后加入左子树,可以保证左子树优先于右子树出栈
Node now = s.pop(); //该操作可以保证保证每次左节点都弹出了
if(now.right != null) s.push(now.right);
if(now.left != null) s.push(now.left);
}
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
//全部路径
private static List<ArrayList<Integer>> result = new ArrayList<>();
//单条路径
private static List<Integer> path = new ArrayList<>();

//递归DFS
public static List<ArrayList<Integer>> findPath(TreeNode root, int target) {
//1.刚进递归函数,就要指明跳出递归的条件
//退出递归的条件:遇到叶子节点(left和right都为null),则返回result
if (null == root) {
return result;
}

//2.处理当前层
//将当前节点加入路径中
path.add(root.val);
//目标值减去当前节点值
target -= root.val;
//如果当前节点是叶子节点,并且路径和为target,将路径加入result中
if (0 == target && null == root.left && null == root.right) {
result.add(new ArrayList<>(path) );
}

//3.递归到下一层
//递归查找当前节点的left和right
findPath(root.left, target);
findPath(root.right, target);

//4.如果有必要,还原当前层状态
//路径中删除当前节点,相当于还原当前层状态
path.remove(path.size() - 1);

return result;
}

}

(1)二叉树的镜像

操作给定的二叉树,将其变换为源二叉树的镜像。

镜像二叉树

思路

递归地进行DFS,只要左子树或右子树不为空,就交换两者。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public static void mirror(TreeNode root) {
//1.退出递归的条件
if (root == null) {
return;
}
//2.处理当前层:只要左右子树不为空,则交换两者
if (root.left != null || root.right != null) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;

//3.drill down
mirror(root.left);
mirror(root.right);
}

//4.还原(此处不需要)
}
}

(2)二叉树的后序遍历

给定一个二叉树,返回它的 后序 遍历。

  • 示例:

  • 进阶:
    递归算法很简单,你可以通过迭代算法完成吗?

思路(递归)
  1. 最简单的方式,使用递归进行DFS遍历即可,但是要注意跳出递归的条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {

private static ArrayList<Integer> result = new ArrayList<>();

//递归-后序遍历
public static ArrayList<Integer> postorderTravelsalWithRecursion(TreeNode root) {
//1.退出递归的条件
if (root == null) {
return result;
}

//3.drill down
if (root.left != null) {
postorderTravelsalWithRecursion(root.left);
}
if (root.right != null) {
postorderTravelsalWithRecursion(root.right);
}

//2.处理当前层(由于是后序遍历,左->右->中,所以当前层要在左右子树处理后才处理)
result.add(root.val);

//4.还原当前层(此处不需要)

return result;
}
}
  1. 但是递归的方式太简单,本题要求使用迭代的方式,而我们都知道尾递归是可以转化成迭代的
  2. 我们采用来实现,既然要求出栈顺序(即后序遍历顺序)为左 -> 右 -> root先入后出,那么入栈顺序应该是root -> 右 -> 左
  3. 使用实现DFS:由于二叉树的特性,必然是根节点最先入栈出栈。如果是先序遍历,那么只需要按照root -> (右 -> 左)循环的顺序入栈,出栈时就是root -> 左 -> 右的顺序。但是如果是后序遍历,那么root最先出栈,需要判断其左、右子树是否已经入栈(通过一个boolean变量进行判断),如果没有,那么root需要重新入栈
代码(栈 + bool
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
static class StackContent {
TreeNode node;
boolean b; //左右节点是否已经入栈标志位

public StackContent(TreeNode node, boolean b) {
this.node = node;
this.b = b;
}
}

public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> rst = new ArrayList<Integer>();
if(root == null) return rst;
Stack<StackContent> stack = new Stack<StackContent>();
stack.push(new StackContent(root, false));

while(!stack.isEmpty() ) {
StackContent now = stack.pop();
//root的左右节点已经入栈
if (now.b) {
//不再入栈
rst.add(now.node.val);
}else{
//root重新入栈
stack.push(new StackContent(now.node, true));
if (now.node.right != null) {
stack.push(new StackContent(now.node.right, false));
}
if (now.node.left != null) {
stack.push(new StackContent(now.node.left, false));
}
}
}
return rst;
}
}

(3)二叉树的先序遍历

给定一个二叉树,返回它的 先序 遍历。

  • 示例:

  • 进阶:
    递归算法很简单,你可以通过迭代算法完成吗?

思路(递归)
  1. 最简单的方式,使用递归进行DFS遍历即可,但是要注意跳出递归的条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {

private static ArrayList<Integer> result = new ArrayList<>();

//递归-先序遍历
public static ArrayList<Integer> preorderTravelsalWithRecursion(TreeNode root) {
//1.退出递归的条件
if (root == null) {
return result;
}

//2.处理当前层(由于是先序遍历,中->左->右,所以当前层要在左右子树之前处理)
result.add(root.val);

//3.drill down
if (root.left != null) {
preorderTravelsalWithRecursion(root.left);
}
if (root.right != null) {
preorderTravelsalWithRecursion(root.right);
}

//4.还原当前层(此处不需要)

return result;
}
}
  1. 但是递归的方式太简单,本题要求使用迭代的方式,而我们都知道尾递归是可以转化成迭代的
  2. 使用实现DFS:由于二叉树的特性,必然是根节点最先入栈出栈。如果是先序遍历,那么只需要按照root -> (右 -> 左)循环的顺序入栈,出栈时就是root -> 左 -> 右的顺序。
代码(栈)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {

private static ArrayList<Integer> result = new ArrayList<>();

//栈-先序遍历
public static ArrayList<Integer> preorderTravelsalWithStack(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();

if (root != null) {
stack.push(root);
}

while (!stack.isEmpty() ) {
//先序遍历:中 -> 左 -> 右
//弹出的栈顶即为:中
TreeNode now = stack.pop();
result.add(now.val);

//接下来需要弹出左 -> 右,所以所以入栈顺序应该为:右 -> 左
if (now.right != null) {
stack.push(now.right);
}
if (now.left != null) {
stack.push(now.left);
}

}
return result;
}
}

(4)二叉树的最近公共祖先

递归DFS

  1. 退出递归的条件:找到了需要查找的节点 / 递归到了叶子节点
  2. 处理当前层 && drill down:判断当前节点左、右子树是否存在需要查找的节点 —— 如果左子树中不存在,那么右孩子就是最近公共祖先;如果右子树中不存在,那么左孩子就是最近公共祖先;如果左右子树中都存在,那么当前节点就是最近公共祖先
  3. 不需要回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//1.退出递归的条件:
//①当前节点为空,无结果
if (root == null) {
return null;
}
//②当前节点为要查找的两个节点中的一个,那么当前节点即为最小公共祖先
if (root == p || root == q) {
return root;
}

//2.处理当前层 && 3.drill down
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
//当前节点左子树没有找到p和q,那么右孩子就是最小公共祖先
if (left == null) {
return right;
}
//当前节点右子树没有找到p和q,那么左孩子就是最小公共祖先
if (right == null) {
return left;
}
//当前节点左子树和右子树都找到了p和q,那么当前节点就是最小公共祖先
return root;
}
}

(二)满二叉树

除了最后一层没有任何子节点外,每一层的所有节点都有两个子节点的二叉树。

满二叉树

完全二叉树

对于深度为k,有n个节点的二叉树,当且仅当它的每一个节点都与深度为k的满二叉树中编号1-n的节点一一对应时才称为完全二叉树。
完全二叉树

-------------本文结束感谢您的阅读-------------

本文标题:算法专题:二叉树(BFS/DFS)(先/中/后序遍历)

文章作者:DragonBaby308

发布时间:2019年08月09日 - 07:34

最后更新:2020年03月01日 - 18:19

原始链接:http://www.dragonbaby308.com/Algorithm-BinaryTree/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%