第三章：二叉树问题（六）
在二叉树中找到一个节点的后继节点
【题目】
现在有一种新的二叉树节点类型如下：
public class Node {
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int data) {
this.value = data;
}
} 该结构比普通二叉树节点结构多了一个指向父节点的parent指针。假设有一棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节点的parent指向null。只给出一个在二叉树中的某个节点node，请实现返回node的后继节点的函数。在二叉树的中序遍历的序列中，node的下一个节点叫作node的后继节点。
例如，如图3-40所示的二叉树。
中序遍历的结果为：1，2，3，4，5，6，7，8，9，10
所以节点1的后继为节点2，节点2的后继为节点3，……，节点10的后继为null。
【难度】
尉 ★★☆☆
【解答】
先简单介绍一种时间复杂度和空间复杂度较高但易于理解的方法。既然新类型的二叉树节点有指向父节点的指针，那么一直往上移动，自然可以找到头节点。找到头节点之后，再进行二叉树的中序遍历，生成中序遍历序列，然后在这个序列中找到node节点的下一个节点返回即可。如果二叉树的节点数为N，这种方法要把二叉树的所有节点至少遍历一遍，生成中序遍历的序列还需要大小为N的空间，所以该方法的时间复杂度与额外空间复杂度都为O(N)。本书不再详述。
最优解法不必遍历所有的节点，如果node节点和node后继节点之间的实际距离为L，最优解法只用走过L个节点，时间复杂度为O(L)，额外空间复杂度为O(1)。接下来详细说明最优解法是如何找到node的后继节点的。
情况1：如果node有右子树，那么后继节点就是右子树上最左边的节点。
例如，题目所示的二叉树中，当node为节点1、3、4、6或9时，就是这种情况。
情况2：如果node没有右子树，那么先看node是不是node父节点的左孩子节点，如果是左孩子节点，那么此时node的父节点就是node的后继节点；如果是右孩子节点，就向上寻找node的后继节点，假设向上移动到的节点记为s，s的父节点记为p，如果发现s是p的左孩子节点，那么节点p就是node节点的后继节点，否则就一直向上移动。
例如，题目所示的二叉树中，当node为节点7时，节点7的父节点是节点8，同时节点7是节点8的左孩子节点，此时节点8就是节点7的后继节点。
再如，题目所示的二叉树中，当node为节点5时，节点5的父节点是节点4，但是节点5是节点4的右孩子节点，所以向上寻找node的后继节点。当向上移动到节点4，节点4的父节点是节点3，但是节点4还是节点3的右孩子节点，继续向上移动。当向上移动到节点3时，节点3的父节点是节点6，此时终于发现节点3是节点6的左孩子节点，移动停止，节点6就是node（节点5）的后继节点。
情况3：如果在情况2中一直向上寻找，都移动到空节点时还是没有发现node的后继节点，说明node根本不存在后继节点。
比如，题目所示的二叉树中，当node为节点10时，一直向上移动到节点6，此时发现节点6的父节点已经为空，说明node没有后继节点。
情况1和情况2遍历的节点就是node到node后继节点这条路径上的节点；情况3遍历的节点数也不会超过二叉树的高度。
最优解的具体过程请参看如下代码中的getNextNode方法。
public Node getNextNode(Node node) {
if (node == null) {
return node;
}
if (node.right != null) {
return getLeftMost(node.right);
} else {
Node parent = node.parent;
while (parent != null && parent.left != node) {
node = parent;
parent = node.parent;
}
return parent;
}
}
public Node getLeftMost(Node node) {
if (node == null) {
return node;
}
while (node.left != null) {
node = node.left;
}
return node;
} 在二叉树中找到两个节点的最近公共祖先
【题目】
给定一棵二叉树的头节点head，以及这棵树中的两个节点o1和o2，请返回o1和o2的最近公共祖先节点。
例如，图3-41所示的二叉树。
节点4和节点5的最近公共祖先节点为节点2，节点5和节点2的最近公共祖先节点为节点2，节点6和节点8的最近公共祖先节点为节点3，节点5和节点8的最近公共祖先节点为节点1。
进阶问题：如果查询两个节点的最近公共祖先的操作十分频繁，想法让单条查询的查询时间减少。
再进阶问题：给定二叉树的头节点head，同时给定所有想要进行的查询。二叉树的节点数量为N，查询条数为M，请在时间复杂度为O(N+M)内返回所有查询的结果。
【难度】
原问题 士 ★☆☆☆
进阶问题 尉 ★★☆☆
再进阶问题 校★★★☆
【解答】
先来解决原问题。后序遍历二叉树，假设遍历到的当前节点为cur。因为是后序遍历，所以先处理cur的两棵子树。假设处理cur左子树时返回节点为left，处理右子树时返回节点为right。
1．如果发现cur等于null，或者o1、o2，则返回cur。
2．如果left和right都为空，说明cur整棵子树上没有发现过o1或o2，返回null。
3．如果left和right都不为空，说明左子树上发现过o1或o2，右子树上也发现过o2或o1，说明o1向上与o2向上的过程中，首次在cur相遇，返回cur。
4．如果left和right有一个为空，另一个不为空，假设不为空的那个记为node，此时node到底是什么？有两种可能，要么node是o1或o2中的一个，要么node已经是o1和o2的最近公共祖先。不管是哪种情况，直接返回node即可。
以题目二叉树的例子来说明一下，假设o1为节点6，o2为节点8，过程为后序遍历。
— 依次遍历节点4、节点5、节点2，都没有发现o1或o2，所以节点1的左子树返回为null；
— 遍历节点6，发现节点6等于o1，返回节点6，所以节点3左子树的返回值为节点6；
— 遍历节点8，发现节点8等于o2，返回节点8，所以节点7左子树的返回值为节点8；
— 节点7的右子树为null，所以节点7右子树的返回值为null；
— 遍历节点7，左子树返回节点8，右子树返回null，根据步骤4，此时返回节点8，所以节点3的右子树的返回值为节点8；
— 遍历节点3，左子树返回节点6，右子树返回节点8，根据步骤3，此时返回节点3，所以节点1的右子树的返回值为节点3；
— 遍历节点1，左子树返回null，右子树返回节点3，根据步骤4，最终返回节点3。
找到两个节点最近公共祖先的详细过程请参看如下代码中的lowestAncestor方法。
public Node lowestAncestor(Node head, Node o1, Node o2) {
if (head == null || head == o1 || head == o2) {
return head;
}
Node left = lowestAncestor(head.left, o1, o2);
Node right = lowestAncestor(head.right, o1, o2);
if (left != null && right != null) {
return head;
}
return left != null ? left : right;
} 进阶问题其实是先花较大的力气建立一种记录，以后执行每次查询时就可以完全根据记录进行查询。记录的方式可以有很多种，本书提供两种记录结构供读者参考，两种记录各有优缺点。
结构一：建立二叉树中每个节点对应的父节点信息，是一张哈希表。
如果对题目中的二叉树建立这种哈希表，哈希表中的信息如下：
| key | value |
| 节点1 | null |
| 节点2 | 节点1 |
| 节点3 | 节点1 |
| 节点4 | 节点2 |
| 节点5 | 节点2 |
| 节点6 | 节点3 |
| 节点7 | 节点3 |
| 节点8 | 节点7 |
key代表二叉树中的一个节点，value代表其对应的父节点。只用遍历一次二叉树，这张表就可以创建好，以后每次查询都可以根据这张哈希表进行。
假设想查节点4和节点8的最近公共祖先，方法是使用如上的哈希表，把包括节点4在内的所有节点4的祖先节点放进另一个哈希表A中，A表示节点4到头节点这条路径上所有节点的集合。所以A={节点4,节点2,节点1}。然后使用如上的哈希表，从节点8开始往上逐渐移动到头节点。首先是节点8，发现不在A中，然后是节点7，发现也不在A中，接下来是节点3，依然不在A中，最后是节点1，发现在A中，那么节点1就是节点4和节点8的最近公共祖先。只要在移动过程中发现某个节点在A中，这个节点就是要求的公共祖先节点。
结构一的具体实现请参看如下代码中Record1类的实现，构造函数是创建记录过程，方法query是查询操作。
public class Record1 {
private HashMap<Node, Node> map;
public Record1(Node head) {
map = new HashMap<Node, Node>();
if (head != null) {
map.put(head, null);
}
setMap(head);
}
private void setMap(Node head) {
if (head == null) {
return;
}
if (head.left != null) {
map.put(head.left, head);
}
if (head.right != null) {
map.put(head.right, head);
}
setMap(head.left);
setMap(head.right);
}
public Node query(Node o1, Node o2) {
HashSet<Node> path = new HashSet<Node>();
while (map.containsKey(o1)) {
path.add(o1);
o1 = map.get(o1);
}
while (!path.contains(o2)) {
o2 = map.get(o2);
}
return o2;
}
}
很明显，结构一建立记录的过程时间复杂度为O(N)、额外空间复杂度为O(N)。进行查询操作时，时间复杂度为O(h)，其中，h为二叉树的高度。
结构二：直接建立任意两个节点之间的最近公共祖先记录，便于以后查询。
建立记录的具体过程如下：
1．对二叉树中的每棵子树（一共N棵）都进行步骤2。
2．假设子树的头节点为h，h所有的后代节点和h节点的最近公共祖先都是h，记录下来。h左子树的每个节点和h右子树的每个节点的最近公共祖先都是h，记录下来。
为了保证记录不重复，设计一种好的实现方式是这种结构实现的重点。
结构二的具体实现请参看如下代码中Record2类的实现。
public class Record2 {
private HashMap<Node, HashMap<Node, Node>> map;
public Record2(Node head) {
map = new HashMap<Node, HashMap<Node, Node>>();
initMap(head);
setMap(head);
}
private void initMap(Node head) {
if (head == null) {
return;
}
map.put(head, new HashMap<Node, Node>());
initMap(head.left);
initMap(head.right);
}
private void setMap(Node head) {
if (head == null) {
return;
}
headRecord(head.left, head);
headRecord(head.right, head);
subRecord(head);
setMap(head.left);
setMap(head.right);
}
private void headRecord(Node n, Node h) {
if (n == null) {
return;
}
map.get(n).put(h, h);
headRecord(n.left, h);
headRecord(n.right, h);
}
private void subRecord(Node head) {
if (head == null) {
return;
}
preLeft(head.left, head.right, head);
subRecord(head.left);
subRecord(head.right);
}
private void preLeft(Node l, Node r, Node h) {
if (l == null) {
return;
}
preRight(l, r, h);
preLeft(l.left, r, h);
preLeft(l.right, r, h);
}
private void preRight(Node l, Node r, Node h) {
if (r == null) {
return;
}
map.get(l).put(r, h);
preRight(l, r.left, h);
preRight(l, r.right, h);
}
public Node query(Node o1, Node o2) {
if (o1 == o2) {
return o1;
}
if (map.containsKey(o1)) {
return map.get(o1).get(o2);
}
if (map.containsKey(o2)) {
return map.get(o2).get(o1);
}
return null;
}
} 如果二叉树的节点数为N，想要记录每两个节点之间的信息，信息的条数为((N-1)´N)/2。所以建立结构二的过程的额外空间复杂度为O(N2)，时间复杂度为O(N2)，单次查询的时间复杂度为O(1)。
再进阶的问题：请参看下一题“Tarjan算法与并查集解决二叉树节点间最近公共祖先的批量查询问题”。
Tarjan算法与并查集解决二叉树节点间最近公共祖先的批量查询问题
【题目】
如下的Node类是标准的二叉树节点结构：
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
} 再定义Query类如下：
public class Query {
public Node o1;
public Node o2;
public Query(Node o1, Node o2) {
this.o1 = o1;
this.o2 = o2;
}
}
一个Query类的实例表示一条查询语句，表示想要查询o1节点和o2节点的最近公共祖先节点。
给定一棵二叉树的头节点head，并给定所有的查询语句，即一个Query类型的数组Query[] ques，请返回Node类型的数组Node[] ans，ans[i]代表ques[i]这条查询的答案，即ques[i].o1和ques[i].o2的最近公共祖先。
【要求】
如果二叉树的节点数为N，查询语句的条数为M，整个处理过程的时间复杂度要求达到O(N+M)。
【难度】
校 ★★★☆
【解答】
本题的解法利用了Tarjan算法与并查集结构的结合。如果读者还不了解什么是并查集，请阅读本书第9章“并查集的实现”。二叉树如图3-42所示，假设想要进行的查询为ques[0]=(节点4和节点7)，ques[1]=(节点7和节点8)，ques[2]=(节点8和节点9)，ques[3]=(节点9和节点3)，ques[4]=(节点6和节点6)，ques[5]=(null和节点5)，ques[6]=(null和null)。
首先生成和ques长度一样的ans数组，如下三种情况的查询是可以直接得到答案的。
1．如果o1等于o2，答案为o1。例如，ques[4]，令ans[4]=节点6。
2．如果o1和o2只有一个为null，答案是不为空的那个。例如，ques[5]，令ans[5]=节点5。
3．如果o1和o2都为null，答案为null。例如，ques[6]，令ans[6]=null。
对不能直接得到答案的查询，我们把查询的格式转换一下，具体过程如下：
1．生成两张哈希表queryMap和indexMap。queryMap类似于邻接表，key表示查询涉及的某个节点，value是一个链表类型，表示key与那些节点之间有查询任务。indexMap的key也表示查询涉及的某个节点，value也是链表类型，表示如果依次解决有关key节点的每个问题，该把答案放在ans的什么位置。也就是说，如果一个节点为node，node与哪些节点之间有查询任务呢？都放在queryMap中；获得的答案该放在ans的什么位置呢？都放在indexMap中。
比如，根据ques[0～3]，queryMap和indexMap生成记录如下：
| Key | Value |
| 节点4 | queryMap中节点4的链表：{节点7} indexMap中节点4的链表：{ 0 } |
| 节点7 | queryMap中节点7的链表：{节点4，节点8} indexMap中节点7的链表：{ 0 ， 1 } |
| 节点8 | queryMap中节点8的链表：{节点7，节点9} indexMap中节点8的链表：{ 1 ， 2 } |
| 节点9 | queryMap中节点9的链表：{节点8，节点3} indexMap中节点9的链表：{ 2 ， 3 } |
| 节点3 | queryMap中节点3的链表：{节点9} indexMap中节点3的链表：{ 3 } |
读者应该会发现一条（o1,o2）的查询语句在上面的两个表中其实生成了两次。这么做的目的是为了处理时方便找到关于每个节点的查询任务，也方便设置答案。介绍完整个流程之后，会有进一步说明。
接下来是Tarjan算法处理M条查询的过程，整个过程是二叉树的先左、再根、再右、最后再回到根的遍历。以图3-42的二叉树来说明。
1）对每个节点生成各自的集合，{1}，{2}，…，{9}，开始时每个集合的祖先节点设为空。
2）遍历节点4，发现它属于集合{4}，设置集合{4}的祖先为节点4，发现有关于节点4和节点7的查询任务，发现节点7属于集合{7}，但集合{7}的祖先节点为空，说明还没遍历到，所以暂时不执行这个查询任务。
2．遍历节点2，发现它属于集合{2}，设置集合{2}的祖先为节点2，此时左孩子节点4属于集合{4}，将集合{4}与集合{2}合并，两个集合一旦合并，小的不再存在，而是生成更大的集合{4,2}，并设置集合{4,2}的祖先为当前节点2。
3．遍历节点7，发现它属于集合{7}，设置集合{7}的祖先为节点7，发现有关节点7和节点4的查询任务，发现节点4属于集合{4,2}，集合{4,2}的祖先节点为节点2，说明节点4和节点7都已经遍历到，根据indexMap知道答案应放在0位置，所以设置ans[0]=节点2；又发现有节点7和节点8的查询任务，发现节点8属于集合{8}，但集合{8}的祖先节点为空，说明还没遍历到，忽略。
4．遍历节点5，发现它属于集合{5}，设置集合{5}的祖先为节点5，此时左孩子节点7属于集合{7}，两集合合并为{7,5}，并设置集合{7,5}的祖先为当前节点5。
5．遍历节点8，发现它属于集合{8}，设置集合{8}的祖先为节点8，发现有节点8和节点7的查询任务，发现节点7属于集合{7,5}，集合{7,5}的祖先节点为节点5，设置ans[1]=节点5；发现有节点8和节点9的查询任务，忽略。
6．从节点5的右子树重新回到节点5，节点5属于{7,5}，节点5的右孩子节点8属于{8}，两个集合合并为{7,5,8}，并设置{7,5,8}的祖先节点为当前的节点5。
7．从节点2的右子树重新回到节点2，节点2属于集合{2,4}，节点2的右孩子节点5属于集合{7,5,8}，合并为{2,4,7,5,8}，并设置这个集合的祖先节点为当前的节点2。
8．遍历节点1，{2,4,7,5,8}与{1}合并为{2,4,7,5,8,1}，这个集合祖先节点为当前的节点1。
9．遍历节点3，发现属于集合{3}，集合{3}祖先节点设为节点3，发现有节点3和节点9的查询任务，但节点9没遍历到，忽略。
10．遍历节点6，发现属于集合{6}，集合{6}祖先节点设为节点6。
11．遍历节点9，发现属于集合{9}，集合{9}祖先节点设为节点9；发现有节点9和节点8的查询任务，节点8属于{2,4,7,5,8,1}，这个集合的祖先节点为节点1，根据indexMap知道答案应放在2位置，所以设置ans[2]=节点1；发现有节点9和节点3的查询任务，节点3属于{3}，这个集合的祖先节点为节点3，根据indexMap，答案应放在3位置，所以设置ans[3]=节点1。
12．回到节点6，合并{6}和{9}为{6,9}，{6,9}的祖先节点设为节点6。
13．回到节点3，合并{3}和{6,9}为{3,6,9}，{3,6,9}的祖先节点设为节点3。
14．回到节点1，合并{2,4,7,5,8,1}和{3,6,9}为{1,2,3,4,5,6,7,8,9}，祖先节点设为节点1。
15．过程结束，所有的答案都已得到。
现在我们可以解释生成queryMap和indexMap的意义了，遍历到一个节点时记为a，queryMap可以让我们迅速查到有哪些节点和a之间有查询任务，如果能够得到答案，indexMap还能告诉我们把答案放在ans的什么位置。假设a和节点b之间有查询任务，如果此时b已经遍历过，自然可以取得答案，然后在有关a的链表中，删除这个查询任务；如果此时b没有遍历过，依然在属于a的链表中删除这个查询任务，这个任务会在遍历到b的时候重新被发现，因为同样的任务b也存了一份。所以遍历到一个节点，有关这个节点的任务列表会被完全清空，可能有些任务已被解决，有些则没有，也不要紧，一定会在后序的过程中被发现并得以解决。这就是queryMap和indexMap生成两遍查询任务信息的意义。
上述流程很好理解，但大量出现生成集合、合并集合和根据节点找到所在集合的操作，如果二叉树的节点数为N，那么生成集合操作O(N)次，合并集合操作O(N)次，根据节点找到所在集合O(N+M)次。所以，如果上述整个过程想达到O(N+M)的时间复杂度，那就要求有关集合的单次操作，平均时间复杂度要求为O(1)。也就是并查集结构。
请读者注意，上述流程中提到一个集合祖先节点的概念与并查集中一个集合代表节点的概念不是一回事。本题的流程中有关设置一个集合祖先节点的操作也不属于并查集自身的操作。下面解释一下在总流程中如何设置一个集合的祖先节点，如上流程中的每一步都有把当前点node所在集合的祖先节点设置为node的操作。在整个流程开始之前，建立一张哈希表，记为 ancestorMap，我们知道，在并查集中，每个集合都是用该集合的代表节点来表示的。所以，如果想把node所在集合的祖先节点设为node，只用把记录（该集合的代表节点, node）放入ancestorMap中即可。同理，如果想得到一个节点a所在集合的祖先节点，先找到节点a的代表节点，然后从ancestorMap中取出相应的记录即可。ancestorMap同时还可以表示一个节点是否被访问过。全部的处理流程请参看如下代码中的tarJanQuery方法。
public class Element<V> {
public V value;
public Element(V value) {
this.value = value;
}
}
public class UnionFindSet<V> {
public HashMap<V, Element<V>> elementMap;
public HashMap<Element<V>, Element<V>> fatherMap;
public HashMap<Element<V>, Integer> rankMap;
public UnionFindSet(List<V> list) {
elementMap = new HashMap<>();
fatherMap = new HashMap<>();
rankMap = new HashMap<>();
for (V value : list) {
Element<V> element = new Element<V>(value);
elementMap.put(value, element);
fatherMap.put(element, element);
rankMap.put(element, 1);
}
}
private Element<V> findHead(Element<V> element) {
Stack<Element<V>> path = new Stack<>();
while (element != fatherMap.get(element)) {
path.push(element);
element = fatherMap.get(element);
}
while (!path.isEmpty()) {
fatherMap.put(path.pop(), element);
}
return element;
}
public V findHead(V value) {
return elementMap.containsKey(value) ? findHead(elementMap
.get(value)).value : null;
}
public boolean isSameSet(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
return findHead(elementMap.get(a)) == findHead(elementMap
.get(b));
}
return false;
}
public void union(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
Element<V> aF = findHead(elementMap.get(a));
Element<V> bF = findHead(elementMap.get(b));
if (aF != bF) {
Element<V> big = rankMap.get(aF) >= rankMap.get(bF) ? aF : bF;
Element<V> small = big == aF ? bF : aF;
fatherMap.put(small, big);
rankMap.put(big, rankMap.get(aF) + rankMap.get(bF));
rankMap.remove(small);
}
}
}
}
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public class Query {
public Node o1;
public Node o2;
public Query(Node o1, Node o2) {
this.o1 = o1;
this.o2 = o2;
}
}
public Node[] tarJanQuery(Node head, Query[] quries) {
HashMap<Node, LinkedList<Node>> queryMap = new HashMap<>();
HashMap<Node, LinkedList<Integer>> indexMap = new HashMap<>();
HashMap<Node, Node> ancestorMap = new HashMap<>();
UnionFindSet<Node> sets = new UnionFindSet<>(getAllNodes(head));
Node[] ans = new Node[quries.length];
setQueriesAndSetEasyAnswers(quries, ans, queryMap, indexMap);
setAnswers(head, ans, queryMap, indexMap, ancestorMap, sets);
return ans;
}
public List<Node> getAllNodes(Node head) {
List<Node> res = new ArrayList<>();
process(head, res);
return res;
}
public void process(Node head, List<Node> res) {
if (head == null) {
return;
}
res.add(head);
process(head.left, res);
process(head.right, res);
}
public void setQueriesAndSetEasyAnswers(Query[] ques, Node[] ans,
HashMap<Node, LinkedList<Node>> queryMap,
HashMap<Node, LinkedList<Integer>> indexMap) {
Node o1 = null;
Node o2 = null;
for (int i = 0; i != ans.length; i++) {
o1 = ques[i].o1;
o2 = ques[i].o2;
if (o1 == o2 || o1 == null || o2 == null) {
ans[i] = o1 != null ? o1 : o2;
} else {
if (!queryMap.containsKey(o1)) {
queryMap.put(o1, new LinkedList<Node>());
indexMap.put(o1, new LinkedList<Integer>());
}
if (!queryMap.containsKey(o2)) {
queryMap.put(o2, new LinkedList<Node>());
indexMap.put(o2, new LinkedList<Integer>());
}
queryMap.get(o1).add(o2);
indexMap.get(o1).add(i);
queryMap.get(o2).add(o1);
indexMap.get(o2).add(i);
}
}
}
public void setAnswers(Node head, Node[] ans,
HashMap<Node, LinkedList<Node>> queryMap,
HashMap<Node, LinkedList<Integer>> indexMap,
HashMap<Node, Node> ancestorMap, UnionFindSet<Node> sets) {
if (head == null) {
return;
}
setAnswers(head.left, ans, queryMap, indexMap, ancestorMap, sets);
sets.union(head.left, head);
ancestorMap.put(sets.findHead(head), head);
setAnswers(head.right, ans, queryMap, indexMap, ancestorMap, sets);
sets.union(head.right, head);
ancestorMap.put(sets.findHead(head), head);
LinkedList<Node> nList = queryMap.get(head);
LinkedList<Integer> iList = indexMap.get(head);
Node node = null;
Node nodeFather = null;
int index = 0;
while (nList != null && !nList.isEmpty()) {
node = nList.poll();
index = iList.poll();
nodeFather = sets.findHead(node);
if (ancestorMap.containsKey(nodeFather)) {
ans[index] = ancestorMap.get(nodeFather);
}
}
} <p> 本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。 同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p> <p> <br /> </p>
