树/图及bfs/dfs

发表于   |   更新于 | 分类于

在开始学习算法至今接近5个月的时间里进步极慢，经过思索还是因为刷题未能集中，无法成体系的进行归纳，今后对算法的学习还是要按照模块来进行，以周为时间单位，争取每周拿下一块知识点。

二叉树的遍历

1. 层序遍历(bfs)

在这里插入图片描述

顾名思义：以层为单位进行遍历，一般使用队列（先进先出）作为遍历的方式

  • 第一层的节点加入队列后，如何遍历第二层呢？

    将根节点从队列中poll出，将poll出的根节点的左右节点加入队列。

  • 如何遍历第三层以至于第n层？

    同样，将第n-1层poll出，对poll出的节点的左右节点add入队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void bfs(node root){
    Queue<node> queue = new ArrayDeque();
    if(root = null){
        return;
    }
    if(root != null){
        queue.add(root);
    }
    while(!queue.isEmpty()){
        node root1 = queue.poll();
        if(root1.left != null){
            queue.add(root1.left);
        }
        if(root1.right != null){
            queue.add(root1.right);
        }
        System.out.print(root1.value+"");
    }
    System.out.println();
}

2. 前中后序遍历（dfs递归）

二叉树dfs的两个要素：访问相邻节点(体现深度优先)和判断base case（递归截止条件）

2.1 前序遍历

https://img-blog.csdnimg.cn/20190820000853382.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx,size_16,color_FFFFFF,t_70

前序遍历的思想类似dfs或者说回溯，递的过程一直往当前节点的左子节点进行遍历，没有就遍历右子节点。归的过程即回溯遍历右子节点。

1
2
3
4
5
6
7
8
public void qianXu(node root){
    if(root == null){
        return;
    }
    System.out.print(root.value+"");
    qianXu(root.left);
    qianXu(root.right);
}

2.2 中序遍历

与前序类似，遍历规则变为“左子树——根节点——右子树”。

在这里插入图片描述

1
2
3
4
5
6
7
public void zhongxu(node root){
    if(root != null){
        zhongxu(root.left);
        System.out.Print(root.value+"");
        zhongxu(root.right);
    }
}

2.3 后序遍历

在这里插入图片描述

1
2
3
4
5
6
7
public void houxu(node root){
    if(root!=null){
        houxu(root.left);
        houxu(root.right);
        System.out.print(root.value+"");
    }
}

3. 前中后序遍历（迭代）

借用栈空间进行遍历

3.1 非递归前序遍历

法一：栈

在这里插入图片描述

区别于递归遍历的顺序，要利用递归的思路，需要先放右节点进栈，再放左节点进栈，然后循环一直到最后会一直优先取到左节点。达到和递归顺序相仿效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void qianxu2(node root){
    Stack<node> s1 = new Stack<node>();
    if(root == null){return;}
    if(root != null){
        s1.push(root);
    }
    while(!s1.isEmpty()){
        node root = s1.pop();
        if(root.right!=null){
            s1.push(root.right);
        }
        if(root.left!=null){
            s1.push(root.left);
        }
        System.out.print(root.value+"");
    }
}

法二：栈，传统方法，先左节点全部入栈，然后遍历其右节点，再向左遍历将左节点进栈。思路完全就是递归的思路。类似于递归实现的栈空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void qianxu3(node root){
    Stack<node> s2 = new Stack<node>();
    while(!s2.isEmpty() || root != null){
        if(root!= null){
            System.out.print(root.value+"");
            s1.push(root);
            root = root.left;
        }else{
            root = s2.pop();
            root = root.right;
        }
    }
}

3.2 非递归中序遍历

和前序类似，就是节点的打印时机应该选在出栈之后，而不是入栈之前。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void zhongxu2(node root){
    Stack<node> s2 = new Stack<node>();
    while(!s2.isEmpty() || root != null){
        if(root!=null){
            s2.push(root);
            root = root.left;
        }else {
            root = s2.pop();
            System.our.print(root.value+"");
            root = root.right;
        }
    }
}

3.3 非递归后序遍历

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void houxu2(node root){
    Stack<node> s3 = new Stack();
    Map<Integer, Integer>map = new HashMap<>();
    while(!s3.isEmpty()||root!=null){
        if(root!=null){
            s3.push(root);
            map.put(root.value, 1);
            root = root.left;
        }else{
            t=q1.peek();
			if(map.get(t.value)==2) {//第二次访问，抛出
				q1.pop();
				System.out.print(t.value+" ");
				t=null;//需要往上走
			}
			else {
				map.put(t.value, 2);
				t=t.right;
			}
        }
    }
}

4. morris遍历方法

Morris遍历使用二叉树节点中大量指向null的指针，时间复杂度：O(n)， 额外空间复杂度：O(1)

在这里插入图片描述

Morris的整体思路就是以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接
我们可以从 图2 看到，如果这么连接之后，cur 这个指针是可以完整的从一个节点顺着下一个节点遍历，将整棵树遍历完毕，直到 7 这个节点右侧没有指向。

如何构造这个网络？

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
public void mirros(node root){
    if(root == null){
        return;
    }
    node cur1 = root;//当前开始遍历的节点
    node cur2 = null;//存放当前节点的左子树
    while(cur1 != null){
        cur2 = cur1.left;
        if(cur2 != null){
            while(cur2.right!=null && cur2.right!=cur1){
            //找到当前左子树的最右侧节点，且这个节点还未与根节点相连
                cur2 = cur2.right;
            }
            if(cur2.right == null){
            //如果最右侧节点的右指针没有指向根节点，创建连接
                cur2.right = cur1;
                cur1 = cur1.left;
                continue;
            }else{//左子树的最右侧节点指向根节点，此时说明我们已经回到了根节点并重复了之前的操作，同时在回到根节点的时候我们应该已经处理完左子树的最右侧节点了，把路断开
                cur2.right = null;
            }
        }
        cur1 = cur1.right;//一直往右边走
    }
}

img

4.1 morris前序遍历

在某个根节点创建连线的时候打印。因为我们是顺着左边的根节点来创建连线，且创建的过程只有一次。

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
public void mirros(node root){
    if(root == null){
        return;
    }
    node cur1 = root;//当前开始遍历的节点
    node cur2 = null;//存放当前节点的左子树
    while(cur1 != null){
        cur2 = cur1.left;
        if(cur2 != null){
            while(cur2.right!=null && cur2.right!=cur1){
            //找到当前左子树的最右侧节点，且这个节点还未与根节点相连
                cur2 = cur2.right;
            }
            if(cur2.right == null){
            //如果最右侧节点的右指针没有指向根节点，创建连接
                cur2.right = cur1;
                System.out.print(cur1.value+"");
                cur1 = cur1.left;
                continue;
            }else{//左子树的最右侧节点指向根节点，此时说明我们已经回到了根节点并重复了之前的操作，同时在回到根节点的时候我们应该已经处理完左子树的最右侧节点了，把路断开,恢复树结构
                cur2.right = null;
            }
        }else{
            System.out.print(cur1.value+"");
        }
        cur1 = cur1.right;//一直往右边走
    }
}

4.2 mirros中序遍历

与前序遍历的区别在于，从左侧开始顺着右节点打印，也就是将cur1切换到上层节点的时候

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
public static void inOrderMorris(TreeNode head) {
	if (head == null) {
		return;
	}
	TreeNode cur1 = head;
	TreeNode cur2 = null;
	while (cur1 != null) {
		cur2 = cur1.left;
		//构建连接线
		if (cur2 != null) {
			while (cur2.right != null && cur2.right != cur1) {
				cur2 = cur2.right;
			}
			if (cur2.right == null) {
				cur2.right = cur1;
				cur1 = cur1.left;
				continue;
			} else {
				cur2.right = null;
			}
		}
		System.out.print(cur1.value + " ");
		cur1 = cur1.right;
	}
}

树的概念分类

  • 树的路径数==叶子节点个数

1. 二叉查找树(BST)

特点：左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大

img

  • bst的遍历

    一般使用中序遍历，可以直接获取元素值排序后的结果

  • bst的查找（O（logn））

    类似于二分查找，每次和根节点比较后，忽略另一半无关节点

    二分查找时间复杂度的计算：

    假设用k次查找到，N/2^k就表示未查找的元素数，对于最坏情况，该值等于1，此时的k = $log_2n$

  • bst的删除

    删除有多个子节点的节点

    删除节点在中序遍历后面的节点中，选择大于删除节点的最小值作为后继节点

基于二叉查找树的这种特点，在查找某个节点的时候，可以采取类似于二分查找的思想，快速找到某个节点。n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 O(logN)。之所以说是正常情况下，是因为二叉查找树有可能出现一种极端的情况（退化为链表），例如：

img

这种情况也是满足二叉查找树的条件，然而，此时的二叉查找树已经近似退化为一条链表，这样的二叉查找树的查找时间复杂度顿时变成了 O(n)。由此必须防止这种情况发生，为了解决这个问题，于是引申出了平衡二叉树。

2. 平衡二叉树（AVL）

特点：

  • 非叶子节点最多拥有两个子节点。
  • 非叶子节点值大于左边子节点、小于右边子节点。
  • 树的左右两边的层级数相差不会大于1。
  • 没有值相等重复的节点。

平衡树的层级结构：平衡二叉树的查询性能和树的层级(高度h)成反比，h值越小查询越快。为了保证树的结构左右两端数据大致平衡。降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如Treap、红黑树。使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找

img

3. 红黑树

为什么有了平衡树还要有红黑树呢？

平衡树的左右层级数不能大于1过于严格，每次插入操作都会破坏原有结构，这时候就需要红黑树进行一下折中

特点：

  • 节点是红色或黑色
  • 根节点是黑色
  • 每个叶子节点都是黑色的空节点
  • 每个红色节点的两个子节点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

img

满足以上的性质，这个二叉树就趋于平衡（注意图中有两个空的叶子节点未画出）

红黑树并不是一个完美平衡二叉查找树，从图1可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。

3.1 自平衡的调整方法（变色和旋转）

  • 变色

    为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。

    下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：

    img

    但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：

img

​ 此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：

img

  • 旋转

    • 左旋

      以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变

    img

    • 右旋

      以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变

    • 总而言之，你当我儿子，我儿子给你当儿子

3.2 红黑树查找

img

和二叉搜索树类似，时间复杂度是O（logn）

3.3 红黑树插入

  • 插入操作包括两部分：

    • 查找插入的位置
    • 插入后自平衡

  • 但插入结点是应该是什么颜色呢？

    答案是红色。理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

  • 插入节点情景分析

    • 红黑树是空树：直接插入作为根节点并设置为黑色

    • 插入节点key已存在：

      将插入节点颜色设置为当前节点颜色；

      replace，更新当前节点的value为插入节点的value

    • 插入节点的父节点为黑色：

      直接插入，不会影响黑色完美平衡

    • 插入节点的父节点为红节点：（祖父节点存在，且为黑色）

      image-20210310104939598

      此时红红相连，红黑树性质被破坏，此时又要细分几种情况

      1. 叔叔节点存在且为红色

        最简单的处理方法是将“黑红红”改为“红黑红”

        image-20210310105326461

        如果pp是跟节点则直接黑化

        pp的父节点是黑色则不影响

        如果此时pp的父节点为红色则还不满足，需要继续进行自平衡处理（右旋？）

1. 无向图

如果一个图结构中，所有的边都没有方向性，那么这种图便称为无向图。典型的无向图，如图所示。由于无向图中的边没有方向性，这样我们在表示边的时候对两个顶点的顺序没有要求

img

2.有向图

一个图结构中，边是有方向性的，那么这种图就称为有向图，如图所示。由于图的边有方向性，我们在表示边的时候对两个顶点的顺序就有要求。我们采用尖括号表示有向边，例如表示从顶点V2到顶点V6，而表示顶点V6到顶点V2。

img

2.1 有向有环图和有向无环图的区别

image-20201221142546739

这两张图对应Leecode上的207课程表问题（下面的专栏第3题），第一张对应返回值为true，第二张对应返回值为false；

对于有向（无环）图来说，可以类似看做是一个树（根节点不一定为1，子节点之间有指向关系），可以通过入度和出度来对顶点进行划分。

3. 顶点的度

连接顶点的边的数量称为该顶点的度。顶点的度在有向图和无向图中具有不同的表示。对于无向图，一个顶点V的度比较简单，其是连接该顶点的边的数量，记为D(V)。 例如，上面所示的无向图中，顶点V5的度为3。而V6的度为2。

对于有向图要稍复杂些，根据连接顶点V的边的方向性，一个顶点的度有入度和出度之分。

  • 入度是以该顶点为端点的入边数量， 记为ID(V)。

  • 出度是以该顶点为端点的出边数量， 记为OD(V)。

    这样，有向图中，一个顶点V的总度便是入度和出度之和，即D(V) = ID(V) + OD(V)。例如，上面所示的有向图中，顶点V5的入度为3,出度为1，因此，顶点V5的总度为4。

4. 邻接顶点

邻接顶点是指图结构中一条边的两个顶点。 邻接顶点在有向图和无向图中具有不同的表示。对于无向图，邻接顶点比较简单。例如，在图二所示的无向图中，顶点V2和顶点V6互为邻接顶点，顶点V2和顶点V5互为邻接顶点等。

对于有向图要稍复杂些，根据连接顶点V的边的方向性，两个顶点分别称为起始顶点(起点或始点)和结束顶点(终点)。有向图的邻接顶点分为两类：

  • 入边邻接顶点：连接该顶点的边中的起始顶点。例如，对于组成这条边的两个顶点，V2是V6的入边邻接顶点。
  • 出边邻接顶点：连接该顶点的边中的结束顶点。例如，对于组成这条边的两个顶点，V6是V2的出边邻接顶点。

bfs专栏

  • bfs通常使用队列或栈等数据结构，通过加以约束的offer和poll实现类似于递归实现的效果，基本可以说是套用模板。。。
  • bfs题目大致分为几类：树形结构（1，2，4），图形结构（3），网格（5）

1. 二叉树的最大深度

递归算法(max+1)较为简单暂且不论，且看用bfs迭代进行遍历的一个变形，就是每次不从队列取出一个，而出取出一层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maxDepth(Node root){
	if(root == null){return 0;}
    Queue<Node> q = new LinkedList<Node>();
    q.offer(root);
    int ans = 0;
    while(!q.isEmpty()){
        int size = q.size();
        while(size>0){
            Node r = q.poll();
            if(r.left!=null){
                q.offer(r.left);
            }
            if(r.right!=null){
                q.offer(r.right);
            }
            size--;
        }
        ans++;     
    }
    return ans;
}

此方法可进行的引申：二叉树的层次遍历,从上到下打印二叉树，

103. 二叉树的锯齿形层次遍历，无非就是加个flag，每层输出的时候正反调换下位置（List接口中的add方法，可以加入索引参数0，是的列表每次从最前面添加，实现倒序输出）

1.1. 二叉树的最小深度

趁热打铁：

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
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int depth = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            ++depth;
            while(size>0){
                TreeNode t = q.poll();
                if(t.left==null&&t.right==null){
                    return depth;
                }
                if(t.left!=null){
                    q.offer(t.left);
                }
                if(t.right!=null){
                    q.offer(t.right);
                }
                --size;
            }
        }
        return depth;
    }
}

2. 对称二叉树

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
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        if(root.left == null&& root.right == null){
            return true;
        }else{
            return check(root.left,root.right);            
        }
    }
    public boolean check(TreeNode a, TreeNode b){
        Queue<TreeNode> q= new LinkedList<TreeNode>();
        //既然让我比较左右是否对称，那我就要把左右对称的节点一起取出来才好比较
        q.offer(a);
        q.offer(b);
        while(!q.isEmpty()){
            l = q.poll();
            r = q.poll();
            if(l==null&&r==null){
                continue;
            }
            if(l==null || r==null || l.val!=r.val){
                return false;
            }
            q.offer(a.left);
            q.offer(b.right);
            q.offer(a.right);
            q.offer(b.left);
        }
    }
}

bfs的模板基本确定，无非就是入队，出队的方式发生些许变化，这题是非常重要的灵活运用bfs方法的体现。

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
37
38
39
40
41
42
class solution{
    List<List<Integer>> edges;
    int[] indeg;
    public boolean canFinish(int numCourses, int[][] prerequisites){
        //edges就是用列表表示的图结构
        edges = new ArrayList<List<Integer>>();
        //索引值即对应每个顶点，add的整型列表即表示顶点对应的入度或出度(这里是出度)
        for(int i=0; i<numCourses; i++){
            edges.add(new ArrayList<Integer>());
        }
        //整型数indeg组索引值对应课程0到numcourses-1顶点，内容对应每个顶点的入度
        indeg = new int[numCourses];
        for(int[] info: prerequisites){
            //info[1]就是先修课程(向外发射的顶点)，info[0]就是后修课程(被指向的顶点)
            edges.get(info[1]).add(info[0]);
            //这里edges的每一项的索引都对应先修课程，内容为需先修该课程的课程队列（或者说索引值对应的顶点所指向的顶点）
            ++indeg[info[0]];
            //这句话就是对入度的计数了
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        //找到入度为0的顶点，加入队列
        for(int i = 0; i<numCourses; ++i){
            if(indeg[i]==0){
                queue.offer(i);
            }
        }
        int visited = 0；
        while (!queue.isEmpty()){
            ++visited;
            int u = queue.poll();
            //找到u所指向的入度高的节点，将其度减一(可以理解为此时将u从图中拿出)，如果度为0，可入队列
            for(int v: edges.get(u)){
                --indeg[v];
                if(indeg[v]==0){
                    queue.offer(v);
                }
            }
        }
		//
        return visited = numCourses;
    }
}

4.员工的重要性

和上面的课程表问题有些类似，高等级员工指向低等级员工，，然后一级一级的向下求和，每一级所对应的节点相互间不存在关系，对应的是树结构

而上面的课程表问题，每节课指向的子节点之间可能也有指向关系，所以对应的是图结构（无向环）

5.岛屿数量

方法；线性扫描整个二维网络，如果一个节点包含1，则以其为根节点启动广度优先搜索。将其放入队列中，并将值设为0以标记访问过该节点。迭代的搜索队列中的每一个节点。直到队列为空。

与树状和图结构的区别：对于队列的while循环需嵌套在对于数组的循环内部

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
class Solution{
    public int numIslands(char[][] grid){
        if(grid==null||grid.length==0){
            return 0;
        }
        int nr = grid.length;//行数
        int nc = grid[0].length;//列数
        int num_island = 0;//声明岛屿个数的变量
        for(int r=0; r<nr; ++r){
            for(int c=0; c<nc; ++c){
                //碰到1即将“岛屿”数加1，更改标记为0，然后启动广度优先搜索
                if(grid[r][c]=='1'){
                    ++num_island;
                    grid[r][c] = '2';
                    //对于数组来说，通过整数获取元素位置的方法！！
                    Queue<Integer> neighbors= new LinkedList<>();
                    neighbors.add(r*nc+c);
                    while(!neighbors.isEmpty()){
                        int id = neighbors.poll();
                        int row = id/nc;
                        int col = id%nc;
                        if(row-1>=0&&grid[row-1][col] == '1'){
                            neighbors.add((row-1)*nc+col);
                            grid[row-1][col] = '0';
                        }                          
                        if(col-1>=0&&grid[row][col-1]=='1'){
                            neighbors.add(row*nc+col-1);
                            grid[row][col-1] = '0';
                        }
                        if(row+1<nr&&grid[row+1][col]=='1'){
                            neighbors.add((row+1)*nc+col);
                            grid[row+1][col] = '0';
                        }
                        if(col+1<nc&&grid[row][col+1]=='1'){
                            neighbors.add(row*nc+col+1);
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }
        return nums_island;
    }
}

dfs专栏

1. 树、图、网格

hot100题中的bfs题刷完，转到dfs这，好嘛，都有重复的，正好再用dfs的方法重温一下，看能否bfs一样归纳出一个递归回溯的模板出来。

  1. 无论树，图，网格，都是先遍历至边界处，然后开始回溯

    重点在于边界的判断方法！！！：

    • 遇null返回(1，1.1，2)，一般对应二叉树结构，即遍历到叶子节点执行回溯
    • for循环无法进行自行返回（3,4，此时的for循环往往为for-each结构），一般对应由List表示的多叉树，图结构，本质上也是遍历到叶子节点执行回溯。以for(String v, u)为例，u即本层遍历节点，v即u指向的下层节点！！！！！
    • 超出网格范围和碰到已遍历过的节点，就执行，本质上也就是对应叶子节点

1. 二叉树的最大深度

回忆一下bfs的解法：通过二叉树的层序遍历方法对二叉树进行遍历，常见depth整型变量，每遍历一层depth++

递归解决和bfs的比较：时间复杂度和空间复杂度相同，bfs是通过从上到下进行depth++，dfs是从下到上depth++

1
2
3
4
5
6
public int maxDepth(TreeNode root){
	if(root == null){
		return 0;
	}
    return Math.max(maxDepth(root.left)+maxDepth(root.right))+1;
}

1.1. 二叉树的最小深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minDepth(TreeNode root) {
		if(root==null) return 0;
        if(root.left==null&&root.right==null) return 1;
        if(root.left!=null&&root.right!=null){
            return Math.min(mindepth(root.left),mindepth(root.right))+1;
        }
        if(root.left!=null){
            return mindepth(root.left)+1;
        }
        if(root.right!=null){
            return mindepth(root.right)+1;
        }
        return 0;
    }
}

2. 对称二叉树

回忆一下dfs的解法：不同于遍历，此时需成对入栈，关键点在于入栈前的判断

bfs和dfs 的对比：判断方法完全相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isMirror(root.left, root.right);
    }
    public boolean isMirror(TreeNode t1, TreeNode t2){
        if(t1 == null && t2 ==null){
            return true;
        }
        if(t1 == null||t2 ==null||t1.val!=t2.val){
            return false;
        }
        return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
    }
}

3. 课程表*

  • 从上面的树结构可以看出：

    bfs都是从上往下逐层进行遍历，dfs则是通过递归，直接搜索到最末断点的叶子节点，然后从下往上进行遍历！！！

  • 映射到图结构上也是一般无二：

    bfs从入度为0的顶点开始展开（类似于树的根节点），然后是入度为1,2,3…（类似于树的层）；

    dfs从出度为0的顶点开始展开（类似于树的叶子节点），然后开始回溯。。。

  • 拓扑排序：对于有向图G

    图 G中的任意一条有向边 (u,v)，u 在排列中都出现在 v 的前面，称该排列为图G的拓扑排序

  • 对于图中的任意一个节点，它在搜索的过程中有三种状态，即：

    「未搜索」：我们还没有搜索到这个节点；

「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成）；

「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。

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
class Solution{
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;
    public boolean canFinish(int numCourses, int[][] prerequisites){
        edges = new ArrayList<List<Integer>>();
        for(int i=0; i<numCourse; ++1){
            edges.add(new ArrayList<Integer>());
        }
        //bfs中的indeg存放入度，这里存放课程是否被访问
        visited = new int[numCourses];
        for(int[] info:prerequisites){
            edges.get(info[1]).add(info[0]);
        }
        //以上部分为图结构的创建
        //对每个节点处都进行一次深度优先搜索
        for(int i=0; i<numCourses&&valid; ++i){
            if(visited[i] == 0){
                dfs(i);
            }
        }
        return valid;
    }
    public void dfs(int u){
        //1：从u这一课程为深度优先搜索的起始点
        visited[u] = 1;
        //注意：他这里没设边界条件，因为搜索到出度为1的节点的时候，edges.get(u)为空，for循环不会执行！！
        for(int v: edges.get(u)){
            //0：代表未被检索，再以其为起点继续dfs
            if(visited[v] == 0){
                dfs(v);
                //假如在执行dfs的过程中碰到了1，即构成了环，也不用多看了，直接返回至起点处，这也是这一判断语句紧跟着dfs()的原因！这么一来直接返回到上面方法中的for循环，直接就返回valid了，真棒！！
                if(!valid){
                    return;
                }
            }else if(visited[v]==1){//代表着找到了环
                valid = false;  
                return;
            }
        }
        //dfs无需返回值，最后出度为0的节点(优先级最高的课)执行结束自动开始回溯
        //回溯过程将从u开始的一条路径上的节点均置为完成搜索。
        visited[u] = 2;
    }
}

4.员工的重要性

n叉树的dfs模板，无参考自行设计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int ans = 0;
    public int getImportance(List<Employee> employees, int id) {
		//同上面的图结构不同，employees中已自带指向的树结构，可直接进行dfs遍历
        for(Employee employee:employees){
            if(employee.id == id){
                ans = ans + employee.importance;
                for(Integer subId: employee.subordinates){
                    getImportance(employees, subId);
                }
            }
        }
        return ans;
    }
}

类似于二叉树的前序遍历，此时的回溯过程都是直接return，当所有叶子节点完成遍历，ans的值就已经确定

稍作修改即可实现类似于上面课程表的后序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int ans = 0;
    public int getImportance(List<Employee> employees, int id) {
		//同上面的图结构不同，employees中已自带指向的树结构，可直接进行dfs遍历
        for(Employee employee:employees){
            if(employee.id == id){
                for(Integer subId: employee.subordinates){
                    getImportance(employees, subId);
                }
                //此时将赋值语句放到递归语句后，则在回溯的过程中执行
                ans = ans + employee.importance;
            }
        }
        return ans;
    }
}

优化方式也是显而易见的，对于二叉树而言，根本不用考虑遍历过节点的重复搜索问题

5.岛屿数量*

这道题就厉害了，网格结构使用dfs的代表之作！！在leetcode上看到了一篇岛屿类问题的通用解法、DFS 遍历框架的文章，且看且分析

  • 网格结构要比二叉树结构稍微复杂一些，其实是一种简化的图结构。
  • 在结合着上面的bfs解法和树结构相联系，bfs就是以一个节点为起始点启动bfs，然后遍历周围4个节点入队列，依次类推，遍历过的打上标记
  • dfs就是选个方向一条道走到头，然后再回头另一个方向走到头。。。

dfs遍历的框架代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    // 如果坐标 (r, c) 超出了网格范围，直接返回
    if (!inArea(grid, r, c)) {
        return;
    }
    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}

避免重复遍历：

之所以说网格结构区别于树，类似于图的原因，就在于其相邻的四个节点都可以构成边，因此就需要将遍历过的节点进行标记，将不需要的边断掉！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    if (!inArea(grid, r, c)) {
        return;
    }
    // 如果这个格子不是岛屿，直接返回
    if (grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 2; // 将格子标记为「已遍历过」
    
    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}

本题代码：

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{
    public int numIslands(char[][] grid){
        int count = 0;
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j] == '1'){
                    dfs(grid, i, j);
                    ++count;
                }
            }
        }
        return count;
    }
    public void dfs(char[][] grid, int r, int c){
        if(!inArea(grid,r,c)){
            return;
        }
        if(grid[r][c]!='1'){  
            return;
        }
        grid[r][c] = '2';
        dfs(grid, r-1, c);
        dfs(grid, r+1, c);
        dfs(grid, r, c-1);
        dfs(grid, r, c+1);            
    }
    public boolean inArea(char[][] grid, int r, int c){
        return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
    }
}

与bfs相比，dfs的速度明显是要快一些！！！

6. 岛屿的周长

此题稍加灵活，算是比较合适的模板练手题目

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
public int islandPerimeter(int[][] grid) {
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                // 题目限制只有一个岛屿，计算一个即可
                return dfs(grid, r, c);
            }
        }
    }
    return 0;
}

int dfs(int[][] grid, int r, int c) {
    // 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边
    if (!inArea(grid, r, c)) {
        return 1;
    }
    // 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边
    if (grid[r][c] == 0) {
        return 1;
    }
    // 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系
    if (grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 2;
    return dfs(grid, r - 1, c)
        + dfs(grid, r + 1, c)
        + dfs(grid, r, c - 1)
        + dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}

2. 排列构成的树形结构

此类问题的常见题型：

对给定范围的数据进行重排，重排过程往往需要实现数据的重复利用，需要由dfs在每一层都进行回溯，从而达到任意排列组合的效果

同样是变形为图结构的题目，但是有其独特的规律可循

解题步骤：

将排列组合看做树结构

  • dfs的截止条件：一般为层数（如1.1字符串全排列），也可能为字符串或列表长度，和层数无关（如2.2数字翻译字符串），也可能与字符串长度和层数同时相关（如2 复原IP）

    **这里需要非常注意的一点是：截止条件就可以作为递归的参数！！！非常方便**

    且在满足截止条件时，一般是一条链遍历结束，需先输出后返回；

  • 候选节点：即该层对应的节点，区别于但又类似于二叉树向下遍历时的root.left，root.right，可用for循环遍历本层的所有节点

    • 候选节点的选择：题目往往会对候选节点加以限制，不然全排过于好做

  • 恢复状态：候选节点的限制往往通过改变其状态实现，在递归函数的代码行后，还需恢复其状态，保证每一次调用时候选列表不会改变

注意点：

回溯过程中的列表是动态变化的，在add到总列表中的时候需要ans.add(new ArrayList(result))！！！！！！！！！

1. 全排列

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
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums){
        boolean[] flag=new boolean[nums.length];
        List<Integer> result= new ArrayList<>();
		dfs(nums, result, flag);
        return ans;
    }
    public void dfs(int[] nums, List<Integer> result, boolean[] flag){
        int n = nums.length;
        //截止条件
        if(result.size()==n){
            ans.add(new ArrayList(result));
            return;
        }
        //遍历该层后选节点
        for(int i=0; i<n; i++){
            //根据题目:候选节点筛选
            if(!flag[i]){
                flag[i] = true;
                result.add(nums[i]);
                dfs(nums, result, flag);
                result.remove(result.size()-1);
                //恢复状态
                flag[i] = false;
            }
        }
    }
}

1.1 全排列优化- 字符串的排列

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
class Solution{
    List<String> ans = new ArrayList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return ans.toArray(new String[0]);
    }
    //看下这里的dfs方法和上面的dfs方法的区别
    //区别1：dfs的参数：不用一堆乱七八糟的，只用层数，结果也不用链表添加存储，直接在原数组c上进行修改
    public void dfs(int floor){
        //区别2：截止条件：因为不引入额外的List或者StringBuffer粘贴每一层的结果，此时直接遍历到最深层就截止
        if(floor = c.length-1){
            ans.add(String.valueOf(c));
        }
        //区别3：候选名单：最关键的剪枝部分。
        //剪枝方法1：每一次的遍历从当前层对应的下标开始，代替上面的用boolean数组记录候选人有没有被选过
        //问题：按理说所有人都有可能成为这层的候选人啊？ 不急，等下还有替换方法，这里的遍历只是对应本层有多少种选择（也就是要选几个人）！！！
       	//剪枝方法2：每层都新建一个列表，遍历一个候选人就填入一个，填入之前判断同一个字母有没有被填过，填过了这个字母就重复了，直接舍弃这种选择，这个列表的作用就是排除在一层里出现重复的情况
        List<Character> can = new ArrayList<>();
        for(int i=floor; i<c.length; ++i){
            if(can.contains(c[i])){
                continue;
            }
           	can.add(c[i]);
            //减小空间复杂度的精髓之处：在原数组上进行变换！！！
            //以0层为例：将1位的字母固定在0的位置上，然后向下一层递，此时下一层拿到的数组c就是换过位的，归的时候将0和1的字母又换回来，进行下一次遍历，此时又是0和2的交换！！
            swap(i, floor);
            dfs(floor+1);
            swap(i, floor);
        }
    }
    public void swap(int a, int b){
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }
}

Picture1.png

Picture2.png

2. 复原IP地址

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
class Solution {
    List<String> ans = new ArrayList<String>();
    int[] split = new int[4];
    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return ans;
    }
    public void dfs(String s, int level, int index) {
        //截止条件
        if(level==4||index==s.length()){
            /*在该条件下的字符串划分满足要求，将其入答案列表后回溯继续执行
              不满足该条件则直接返回*/
            if(level==4&&index==s.length()){
                StringBuffer result = new StringBuffer();
                for(int i=0; i<4; i++){
					result.append(split[i]);
                    if(i<3) result.append('.');
                }
                ans.add(result.toString());
            }
            return;
        }
        if(s.charAt(index)=='0'){
            split[level] = 0;
            dfs(s,level+1,index+1);
        }
        int addr = 0;
        //候选节点
        for(int i=index; i<s.length(); i++){
            //筛选
            addr = addr*10+(s.charAt(i)-'0');
            if(addr>0&&addr<256){
                split[level] = addr;
                dfs(s,level+1,i+1);
            }else{
                break;
            }
        }
    }
}

2.2 把数字翻译成字符串

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
class Solution {
    public char[] c;
    public List<String> l = new ArrayList<>();
    public StringBuffer sb = new StringBuffer();
    public int translateNum(int num) {
        String ns = String.valueOf(num);
        c = ns.toCharArray();
        service(sb,0);
        return l.size();
    }
    public void service(StringBuffer sb, int len){
        if(len>=c.length) {
            l.add(sb.toString());
            return;
        }
        sb.append((char)(c[len]-'0'+'a'));
        service(sb,len+1);
        if(c[len]-'0'<=2 && c[len]-'0'>0 && len<c.length-1 && c[len+1]-'0'<6){
            String a="";
            int b = Integer.parseInt(a+c[len]+c[len+1]);
            sb.append(b+'a');
            service(sb,len+2);
        }
        return;
    }
}

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
class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0){
            return ans;
        }
        //匿名内部类
        Map<Character, String> phone = new HashMap<Character, String>(){{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        StringBuffer result = new StringBuffer();
		dfs(digits,0,result,phone);
        return ans;                                                                        
    }
    public void dfs(String digits, int index, StringBuffer result, Map<Character, String> phone){
        if(digits.length()==index){
            ans.add(result.toString());
            return;
        }
        char digit = digits.charAt(index);
        for(char a: phone.get(digit).toCharArray()){
            result.append(a);
            dfs(digits,index+1,result,phone);
            result.deleteCharAt(index);
        }
    }
}

4. 组合总和

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
class Solution {
    List<List<Integer>> ans  = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> result = new ArrayList<>();
        dfs(target, candidates, result, 0, 0);
        return ans;
    }
    public void dfs(int target, int[] candidates, List<Integer> result, int and,int index){
        //截止条件
        if(and >= target){
            if(and == target){
                ans.add(new ArrayList<>(result));
            }
            return;
        }
        /*因为答案要求结果不重复，index在这里就起到减枝的作用，每一个节点的子节点个数和其位置有关
        比如2的子节点就是2,3,6,7；3的子节点就是3,6,7；6的子节点就是6,7。。。*/
        for(int i = index; i<candidates.length; ++i){
            if(and+candidates[i]<=target){
                result.add(candidates[i]);
                dfs(target,candidates,result,and+candidates[i],i);
                result.remove(result.size()-1);
            }
        }
    }
}

5. 括号生成

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
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }
	//因为已有的左右括号数量对后序候选节点的筛选起作用，所以定义open和close跟踪目前的节点数量
    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        //截止条件
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        //候选节点！！！可以看出候选节点可以根据筛选条件分开操作！！！
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

6. 所有可能的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int[] visited = new int[graph.length];
        List<Integer> result = new ArrayList<>();
        dfs(graph,visited,0,result);
        return ans;
    }
    public void dfs(int[][] graph, int[] visited, int level, List<Integer> result){
        if(visited[level]!=0) return;
        visited[level]=1;
        result.add(level); 
        if(level==graph.length-1){
            ans.add(new ArrayList(result));
        }
        for(int x: graph[level]){
            dfs(graph,visited,x,result);
        }
        result.remove(result.size()-1);
        visited[level] =0;
    }
}

. 二叉树展开为链表

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
//方法1：递归的栈结构
class Solution {
    public void flatten(TreeNode root) {
		if(root == null){
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.right = last;
        root.left = null;
        last = root;
    }
}
//方法2：常规解法-二叉树的前序遍历
class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        root = link(root);
    }
    public TreeNode link(TreeNode root){
        if(root == null){
            return null;
        }
        TreeNode l = link(root.left);
        TreeNode r = link(root.right);
        if(l == null){
            root.right = r;
        }else{
            TreeNode cur = l;
            while(cur.right!=null){
                cur = cur.right;
            }
            cur.right = r;
            root.right = l;
            root.left = null;
        }
        return root;
    }
}