第三章：二叉树问题（三）
在二叉树中找到累加和为指定值的最长路径长度
【题目】
给定一棵二叉树的头节点head和一个32位整数sum，二叉树节点值类型为整型，求累加和为sum的最长路径长度。路径是指从某个节点往下，每次最多选择一个孩子节点或者不选所形成的节点链。
例如，二叉树如图3-16所示。
如果sum=6，那么累加和为6的最长路径为：-3，3，0，6，所以返回4。
如果sum=-9，那么累加和为-9的最长路径为：-9，所以返回1。
注：本题不用考虑节点值相加可能溢出的情况。
【难度】
尉 ★★☆☆
【解答】
在阅读本题的解答之前，请读者先阅读本书“求未排序数组中累加和为规定值的最长子数组长度”问题。针对二叉树，本文的解法改写了这个问题的实现。如果二叉树的节点数为N，本文的解法可以做到时间复杂度为O(N)，额外空间复杂度为O(h)，其中，h为二叉树的高度。
具体过程如下：
1．二叉树头节点head和规定值sum已知；生成变量maxLen，负责记录累加和等于sum的最长路径长度。
2．生成哈希表sumMap。在“求未排序数组中累加和为规定值的最长子数组长度”问题中也使用了哈希表，功能是记录数组从左到右的累加和出现情况，在遍历数组的过程中，再利用这个哈希表来求得累加和为规定值的最长子数组。sumMap也一样，它负责记录从head开始的一条路径上的累加和出现的情况，累加和也是从head节点的值开始累加的。sumMap的key值代表某个累加和，value值代表这个累加和在路径中最早出现的层数。如果在遍历到cur节点时，我们能够知道从head到cur节点这条路径上的累加和出现的情况，那么求以cur节点结尾的累加和为指定值的最长路径长度就非常容易。究竟如何去更新sumMap，才能够做到在遍历到任何一个节点时都能有从head到这个节点的路径上的累加和出现的情况呢？步骤3详细地说明了更新过程。
3．首先在sumMap中加入一个记录(0,0)，它表示累加和0不用包括任何节点就可以得到。然后按照二叉树先序遍历的方式遍历节点，遍历到的当前节点记为cur，从head到cur父节点的累加和记为preSum，cur所在的层数记为level。将cur.value+preSum的值记为curSum，就是从head到cur的累加和。如果sumMap中已经包含了curSum的记录，则说明curSum在上层中已经出现过，那么就不更新sumMap；如果sumMap不包含curSum的记录，则说明curSum是第一次出现，就把（curSum,level）这个记录放入sumMap。接下来是求解在必须以cur结尾的情况下，累加和为规定值的最长路径长度，详细过程这里不再详述，请读者阅读“求未排序数组中累加和为规定值的最长子数组长度”问题。然后是遍历cur左子树和右子树的过程，依然按照上述方法使用和更新sumMap。处理完以cur为头节点的子树，当然要返回cur父节点，在返回前还有一项重要的工作要做，在sumMap中查询curSum这个累加和（key）出现的层数（value），如果value等于level，则说明curSum这个累加和的记录是在遍历到cur时加上去的，那就把这条记录删除；如果value不等于level，则不做任何调整。
4．步骤3会遍历二叉树所有的节点，也会求解以每个节点结尾的情况下，累加和为规定值的最长路径长度。用maxLen记录其中的最大值即可。
全部求解过程请参看如下代码中的getMaxLength方法。
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public int getMaxLength(Node head, int sum) {
HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
sumMap.put(0, 0); // 重要
return preOrder(head, sum, 0, 1, 0, sumMap);
}
public int preOrder(Node head, int sum, int preSum, int level,
int maxLen, HashMap<Integer, Integer> sumMap) {
if (head == null) {
return maxLen;
}
int curSum = preSum + head.value;
if (!sumMap.containsKey(curSum)) {
sumMap.put(curSum, level);
}
if (sumMap.containsKey(curSum - sum)) {
maxLen = Math.max(level - sumMap.get(curSum - sum), maxLen);
}
maxLen = preOrder(head.left, sum, curSum, level + 1, maxLen, sumMap);
maxLen = preOrder(head.right, sum, curSum, level + 1, maxLen, sumMap);
if (level == sumMap.get(curSum)) {
sumMap.remove(curSum);
}
return maxLen;
} 找到二叉树中的最大搜索二叉子树
【题目】
给定一棵二叉树的头节点head，已知其中所有节点的值都不一样，找到含有节点最多的搜索二叉子树，并返回这棵子树的头节点。
例如，二叉树如图3-17所示。
这棵树中的最大搜索二叉子树如图3-18所示。
【要求】
如果节点数为N，则要求时间复杂度为O(N)，额外空间复杂度为O(h)，h为二叉树的高度。
【难度】
尉 ★★☆☆
【解答】
本题涉及二叉树面试题中一个很常见的套路，也是全书的一个重要内容。利用分析可能性求解在二叉树上做类似动态规划的问题。请读者理解并学习这种套路，本章还有很多面试题目是用这个套路求解的，我们把这个套路的名字叫作树形dp套路。
树形dp套路使用前提：如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在S规则下的每一个答案，并且最终答案一定在其中。
如何理解这个前提呢？以本题为例，题目求解目标是：整棵二叉树中的最大搜索二叉子树，这就是我们的规则。那么求解流程可不可以定成：在整棵二叉树中，求出每一个节点为头节点的子树的最大搜索二叉子树（对任何一棵子树都求出答案），并且最终答案（整棵二叉树的最大搜索二叉子树）一定在其中？当然可以。因此，本题可以使用套路。
树形dp套路第一步：以某个节点X为头节点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性的。用本题举例。
以节点X为头节点的子树中，最大的搜索二叉子树只可能是以下三种情况中可能性最大的那种。
第一种：X为头节点的子树中，最大的搜索二叉子树就是X的左子树中的最大搜索二叉子树。也就是说，答案可能来自左子树。比如，本例中，当X为节点12时。
第二种：X为头节点的子树中，最大的搜索二叉子树就是X的右子树中的最大搜索二叉子树。也就是说，答案可能来自右子树。比如，本例中，当X为节点6时。
第三种：如果X左子树上的最大搜索二叉子树是X左子树的全体，X右子树上的最大搜索二叉子树是X右子树的全体，并且X的值大于X左子树所有节点的最大值，但小于X右子树所有节点的最小值，那么X为头节点的子树中，最大的搜索二叉子树就是以X为头节点的全体。也就是说，答案可能是用X连起所有。比如，本例中，当X为节点10时。
树形dp套路第二步：根据第一步的可能性分析，列出所有需要的信息。用本题举例，为了分析第一、二种可能性，需要分别知道左子树和右子树上的最大搜索二叉子树的头部，记为leftMaxBSTHead、rightMaxBSTHead，因为要比较大小，所以还需要分别知道左子树和右子树上的最大搜索二叉子树的大小，记为leftBSTSize、rightBSTSize，并且有了这些信息还能帮助分析第三种可能性，因为如果知道了leftMaxBSTHead，并且发现它正好是X的左孩子节点，则说明X左子树上的最大搜索二叉子树是X左子树的全体。同理，可以利用rightMaxBSTHead来判断X右子树上的最大搜索二叉子树是否为X右子树的全体。但是有这些还不够，因为第三种可能性还要求X的值大于X左子树所有节点的最大值，但小于X右子树所有节点的最小值。因此，需要从左子树上取得左子树的最大值leftMax，从右子树上取得右子树的最小值rightMin。汇总一下，为了分析所有的可能性，左树上需要的信息为：leftMaxBSTHead、leftBSTSize、leftMax；右树上需要的信息为：rightMaxBSTHead、rightBSTSize、rightMin。
树形dp套路第三步：合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构。以本题举例，左树和右树都需要最大搜索二叉子树的头节点及其大小这两个信息，但是左树只需要最大值，右树只需要最小值，那么合并变成统一要求。信息结构请看如下的ReturnType类。
public class ReturnType {
public Node maxBSTHead;
public int maxBSTSize;
public int min;
public int max;
public ReturnType(Node maxBSTHead, int maxBSTSize, int min, int max) {
this.maxBSTHead = maxBSTHead;
this.maxBSTSize = maxBSTSize;
this.min = min;
this.max = max;
}
} 树形dp套路第四步：设计递归函数，递归函数是处理以X为头节点的情况下的***括设计递归的base case，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构这四个小步骤。本题的实现请看如下的process方法。
public ReturnType process(Node X) {
// base case : 如果子树是空树
// 最小值为系统最大
// 最大值为系统最小
if (X == null) {
return new ReturnType(null, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
}
// 默认直接得到左树全部信息
ReturnType lData = process(X.left);
// 默认直接得到右树全部信息
ReturnType rData = process(X.right);
// 以下过程为信息整合
// 同时对以X为头节点的子树也做同样的要求，也需要返回如ReturnType描述的全部信息
// 以X为头节点的子树的最小值是：左树最小、右树最小及X的值三者中最小的
int min = Math.min(X.value, Math.min(lData.min, rData.min));
// 以X为头节点的子树的最大值是：左树最大、右树最大及X的值三者中最大的
int max = Math.max(X.value, Math.max(lData.max, rData.max));
// 如果只考虑可能性一和可能性二，则以X为头节点的子树的最大搜索二叉树大小
int maxBSTSize = Math.max(lData.maxBSTSize, rData.maxBSTSize);
// 如果只考虑可能性一和可能性二，则以X为头节点的子树的最大搜索二叉树头节点
Node maxBSTHead = lData.maxBSTSize >= rData.maxBSTSize ? lData.maxBSTHead
: rData.maxBSTHead;
// 利用收集的信息，可以判断是否存在第三种可能性
if (lData.maxBSTHead == X.left && rData.maxBSTHead == X.right
&& X.value > lData.max && X.value < rData.min) {
maxBSTSize = lData.maxBSTSize + rData.maxBSTSize + 1;
maxBSTHead = X;
}
// 信息全部收集完毕，返回
return new ReturnType(maxBSTHead, maxBSTSize, min, max);
}
树形dp套路就是以上四个步骤，就是利用递归函数设计一个二叉树后序遍历的过程：先遍历左子树收集信息，然后是右子树收集信息，最后在头节点做信息整合。因为是递归函数，所以对所有的子树要求一样，都返回ReturnType的实例。依次求出每棵子树的答案，总答案一定在其中。既然是后序遍历，则时间复杂度为O(N)。主方法如下。
public Node getMaxBST(Node head) {
return process(head).maxBSTHead;
} 找到二叉树中符合搜索二叉树条件的最大拓扑结构
【题目】
给定一棵二叉树的头节点head，已知所有节点的值都不一样，返回其中最大的且符合搜索二叉树条件的最大拓扑结构的大小。
例如，二叉树如图3-19所示。
其中最大的且符合搜索二叉树条件的拓扑结构如图3-20所示。
这个拓扑结构节点数为8，所以返回8。
【难度】
校 ★★★☆
【解答】
方法一：二叉树的节点数为N，时间复杂度为O(N2)的方法。
首先来看这样一个问题，以节点h为头节点的树中，在拓扑结构中也必须以h为头节点的情况下，怎么找到符合搜索二叉树条件的最大结构？这个问题有一种比较容易理解的解法，我们先考查h的孩子节点，根据孩子节点的值从h开始按照二叉搜索的方式移动，如果最后能移动到同一个孩子节点上，说明这个孩子节点可以作为这个拓扑的一部分，并继续考查这个孩子节点的孩子节点，一直延伸下去。
我们以题目的例子来说明一下，假设在以12这个节点为头节点的子树中，要求拓扑结构也必须以12为头节点，如何找到最多的节点，并且整个拓扑结构是符合二叉树条件的？初始时考查的节点为12节点的左右孩子节点，考查队列={10,13}。
考查节点10。最开始是节点10和节点12进行比较，发现节点10应该往节点12的左边找，于是节点10被找到，节点10可以加入整个拓扑结构，同时将节点10的孩子节点4和14加入考查队列，考查队列为{13,4,14}。
考查节点13。节点13和节点12进行比较，应该向右，于是节点13被找到，它可以加入整个拓扑结构，同时将它的两个孩子节点20和16加入考查队列，为{4,14,20,16}。
考查节点4。节点4和节点12比较，应该向左，节点4和节点10比较，继续向左，节点4被找到，可以加入整个拓扑结构。同时将它的孩子节点2和5加入考查队列，为{14,20,16,2,5}。
考查节点14。节点14和节点12比较，应该向右，接下来的查找过程会一直在节点12的右子树上，依然会找下去，但是节点14不可能被找到。所以它不能加入整个拓扑结构，它的孩子节点也都不能，此时考查队列为{20,16,2,5}。
考查节点20。节点20和节点12比较，应该向右，节点20和节点13比较，继续向右，节点20同样再也不会被发现了，所以它不能加入整个拓扑结构，此时，考查队列为{16,2,5}。
按照如上方法，最后这三个节点（16,2,5）都可以加入拓扑结构，所以我们找到了必须以12为头节点，且整个拓扑结构是符合二叉树条件的最大结构，这个结构的节点数为7。
也就是说，我们根据一个节点的值，根据这个值的大小，从h开始，每次向左或者向右移动，如果最后能移动到原来的节点上，说明该节点可以作为以h为头节点的拓扑的一部分。
解决了以节点h为头节点的树中，在拓扑结构也必须以h为头节点的情况下，怎么找到符合搜索二叉树条件的最大结构？接下来只要遍历所有的二叉树节点，并在以每个节点为头节点的子树中都求一遍其中的最大拓扑结构，其中最大的那个就是我们想找的结构，它的大小就是返回值。
具体过程请参看如下代码中的bstTopoSize1方法。
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public int bstTopoSize1(Node head) {
if (head == null) {
return 0;
}
int max = maxTopo(head, head);
max = Math.max(bstTopoSize1(head.left), max);
max = Math.max(bstTopoSize1(head.right), max);
return max;
}
public int maxTopo(Node h, Node n) {
if (h != null && n != null && isBSTNode(h, n, n.value)) {
return maxTopo(h, n.left) + maxTopo(h, n.right) + 1;
}
return 0;
}
public boolean isBSTNode(Node h, Node n, int value) {
if (h == null) {
return false;
}
if (h == n) {
return true;
}
return isBSTNode(h.value > value ? h.left : h.right, n, value);
}
对于方法一的时间复杂度分析，我们把所有的子树（N个）都找了一次最大拓扑，每找一次，所考查的节点数都可能是O(N)个节点，所以方法一的时间复杂度为O(N2)。
方法二：二叉树的节点数为N，时间复杂度为O(N)的方法。
先来说明一个对方法二来讲非常重要的概念——拓扑贡献记录。还是举例说明，请注意题目中以节点10为头节点的子树，这棵子树本身就是一棵搜索二叉树，那么整棵子树都可以作为以节点10为头节点的符合搜索二叉树条件的拓扑结构。如果对如图3-19所示的拓扑结构建立贡献记录，则是如图3-21所示的样子。
在图3-21中，每个节点的旁边都有被括号括起来的两个值，我们把它称为节点对当前头节点的拓扑贡献记录。第一个值代表节点的左子树可以为当前头节点的拓扑贡献几个节点，第二个值代表节点的右子树可以为当前头节点的拓扑贡献几个节点。比如，4(1,1)括号中的第一个1代表节点4的左子树可以为节点10为头的拓扑结构贡献1个节点，第二个1代表节点4的右子树可以为节点10为头节点的拓扑结构贡献1个节点。同样，我们也可以建立以节点13为头节点的记录，如图3-22所示。
整个方法二的核心就是如果分别得到了h左右两个孩子节点为头节点的拓扑贡献记录，可以快速得到以h为头节点的拓扑贡献记录。比如图3-21中每一个节点的记录都是节点对以节点10为头节点的拓扑结构的贡献记录，图3-22中每一个节点的记录都是节点对以节点13为头节点的拓扑结构的贡献记录，同时节点10和节点13分别是节点12的左孩子节点和右孩子节点。那么我们可以快速得到以节点12为头节点的拓扑贡献记录。在图3-21和图3-22中所有节点的记录还没有变成节点12为头节点的拓扑贡献记录之前，是如图3-23所示的样子。
如图3-23所示，在没有变更之前，节点12左子树上所有节点的记录和原来一样，都是对节点10负责的；节点12右子树上所有节点的记录也和原来一样，都是对节点13负责的。接下来详细展示一下，所有节点的记录如何变更为都对节点12负责，也就是所有节点的记录都变成以节点12为头节点的拓扑贡献记录。
先来看节点12的左子树，只需依次考查左子树右边界上的节点即可。先考查节点10，因为节点10的值比节点12的值小，所以节点10的左子树原来能给节点10贡献多少个节点，当前就一定都能贡献给节点12，这样节点10记录的第一个值不用改变，同时节点10左子树上所有节点的记录都不用改变。接下来考查节点14，此时节点14的值比节点10要大，说明以节点14为头节点的整棵子树都不能成为以节点12为头节点的拓扑结构的左边部分，那么删掉节点14的记录，让它不作为节点12为头节点的拓扑结构即可，同时只要删掉节点14一条记录，就可以断开节点11和节点15的记录，让节点14的整棵子树都不成为节点12的拓扑结构，且后续的右边界节点也无须考查了。进行到节点14这一步，一共删掉的节点数可以直接通过节点14的记录得到，记录为14(1,1)，说明节点14的左子树1个，节点14的右子树1个，再加上节点14本身，一共有3个节点。接下来的过程是从右边界的当前节点重回节点12的过程，先回到节点10，此时节点10记录的第二个值应该被修改，因为节点10的右子树上被删掉了3个节点，所以记录由10(3,3)修改为10(3,0)，根据这个修改后的记录，节点12记录的第一个值也可以确定了，节点12的左子树可以贡献4个节点，其中3个来自节点10的左子树，还有1个是节点10本身，此时记录变为如图3-24所示的样子。
以上过程展示了怎么把关于h左孩子节点的拓扑贡献记录更改为以h为头节点的拓扑贡献记录。为了更好地展示这个过程，我们再举一个例子，如图3-25所示。
在图3-25中，假设之前已经有以节点A为头节点的拓扑贡献记录，现在要变更为以节点S为头节点的拓扑贡献记录。只用考查S左子树的右边界即可（A,B,C,D...），假设A，B，C的值都比S小，到节点D才比节点S大。那么A、B、C的左子树原来能给A的拓扑贡献多少个节点，现在就都同样能贡献给S，所以这三个节点记录的第一个值一律不发生变化，并且它们所有左子树上的节点记录也不用变化。而D的值比S的值大，所以删除D的记录，从而让D子树上的所有记录都和以S为头节点的拓扑结构断开，总共删掉的节点数为d1+d2+1。然后从C回到S，沿途所有节点记录的第二个值统一减掉d1+d2+1。最后根据节点A改变后的记录，确定S记录的第一个值，如图3-26所示。
关于怎么把h左孩子节点的拓扑贡献记录更改为以h为头节点的拓扑贡献记录的问题就解释完了。把关于h右孩子节点的拓扑贡献记录更改为以h为头节点的拓扑贡献记录与之类似问题，就是依次考查h右子树的左边界即可。回到以节点12为头节点的拓扑贡献记录问题，最后生成的整个记录如图3-27所示。
当我们得到以h为头节点的拓扑贡献记录后，相当于求出了以h为头节点的最大拓扑的大小。方法二正是不断地用这种方法，从小树的记录整合成大树的记录，从而求出整棵树中符合搜索二叉树条件的最大拓扑的大小。因此，整个过程大体说来是利用二叉树的后序遍历，对每个节点来说，首先生成其左孩子节点的记录，然后是右孩子节点的记录，接着把两组记录修改成以这个节点为头的拓扑贡献记录，并找出所有节点的最大拓扑结构中最大的那个。
方法二的全部过程请参看如下代码中的bstTopoSize2方法。
public class Record {
public int l;
public int r;
public Record(int left, int right) {
this.l = left;
this.r = right;
}
}
public int bstTopoSize2(Node head) {
Map<Node, Record> map = new HashMap<Node, Record>();
return posOrder(head, map);
}
public int posOrder(Node h, Map<Node, Record> map) {
if (h == null) {
return 0;
}
int ls = posOrder(h.left, map);
int rs = posOrder(h.right, map);
modifyMap(h.left, h.value, map, true);
modifyMap(h.right, h.value, map, false);
Record lr = map.get(h.left);
Record rr = map.get(h.right);
int lbst = lr == null ? 0 : lr.l + lr.r + 1;
int rbst = rr == null ? 0 : rr.l + rr.r + 1;
map.put(h, new Record(lbst, rbst));
return Math.max(lbst + rbst + 1, Math.max(ls, rs));
}
public int modifyMap(Node n, int v, Map<Node, Record> m, boolean s) {
if (n == null || (!m.containsKey(n))) {
return 0;
}
Record r = m.get(n);
if ((s && n.value > v) || ((!s) && n.value < v)) {
m.remove(n);
return r.l + r.r + 1;
} else {
int minus = modifyMap(s ? n.right : n.left, v, m, s);
if (s) {
r.r = r.r - minus;
} else {
r.l = r.l - minus;
}
m.put(n, r);
return minus;
}
}
下面介绍方法二的时间复杂度分析。假设二叉树如图3-28所示。
方法二就是对任何一个节点，遍历这个节点的左子树的右边界和右子树的左边界。我们首先看遍历所有节点左子树的右边界的代价。
节点1左子树的右边界：2 -> 5 -> 11； 节点2左子树的右边界：4 -> 9；
节点3左子树的右边界：6 -> 13； 节点4左子树的右边界：8；
节点5左子树的右边界：10； 节点6左子树的右边界：12；
节点7左子树的右边界：14。
可以看出，所有右边界的所有节点数量为O(N)，那么遍历所有节点左子树右边界的总代价为O(N)。同理，遍历所有节点右子树左边界的总代价为O(N)。因此，方法二的时间复杂度为O(N)。
<p> 本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。 同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p> <p> <br /> </p>
查看42道真题和解析
