第三章：二叉树问题（七）
二叉树节点间的最大距离问题
【题目】
从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫作A到B的距离。
比如，图3-43所示的二叉树，节点4和节点2的距离为2，节点5和节点6的距离为5。给定一棵二叉树的头节点head，求整棵树上节点间的最大距离。
【要求】
如果二叉树的节点数为N，时间复杂度要求为O(N)。
【难度】
尉 ★★☆☆
【解答】
本题解法的整体过程为树形dp套路，请读者先阅读本书“找到二叉树中的最大搜索二叉子树”问题了解这个套路，本题是这个套路的再一次展示。首先本题对于树形dp套路前提是满足的：依次求出每一个节点为头节点的子树上的最大距离，那么最终答案一定在其中。
树形dp套路第一步：以某个节点X为头节点的子树中，分析答案来自哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性的。
可能性一：以X为头节点的子树，最大距离可能是左子树上的最大距离。
可能性二：以X为头节点的子树，最大距离可能是右子树上的最大距离。
可能性三：以X为头节点的子树，最大距离可能是从X的左子树离X最远的节点，先到达X，然后走到X的右子树离X最远的节点。也就是左子树高度+右子树高度+1。
树形dp套路第二步：根据第一步的可能性分析，列出所有需要的信息。左子树和右子树都需要知道自己这棵子树上的最大距离，以及高度这两个信息。
树形dp套路第三步：根据第二步信息汇总。定义信息如ReturnType类所示。
public class ReturnType {
public int maxDistance;
public int height;
public ReturnType(int maxDistance, int height) {
this.maxDistance = maxDistance;
this.height = height;
}
} 树形dp套路第四步：设计递归函数。递归函数是处理以X为头节点的情况下的***括设计递归的base case、默认直接得到左树和右树的所有信息，以及把可能性做整合，并且也要返回第三步的信息结构这四个小步骤。本题的递归实现请看以下的process方法，主函数是以下的getMaxDistance方法。
public ReturnType process(Node head) {
if (head == null) {
return new ReturnType(0, 0);
}
ReturnType leftData = process(head.left);
ReturnType rightData = process(head.right);
int height = Math.max(leftData.height, rightData.height) + 1;
int maxDistance = Math.max(leftData.height + rightData.height + 1,
Math.max(leftData.maxDistance, rightData.maxDistance));
return new ReturnType(maxDistance, height);
}
public int getMaxDistance(Node head) {
return process(head).maxDistance;
} 派对的最大快乐值
【题目】
员工信息的定义如下：
class Employee {
public int happy; // 这名员工可以带来的快乐值
List<Employee> subordinates; // 这名员工有哪些直接下级
} 公司的每个员工都符合Employee类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板，除老板外，每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工（subordinates列表为空），除基层员工外，每个员工都有一个或多个直接下级。
这个公司现在要办party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下规则。
1．如果某个员工来了，那么这个员工的所有直接下级都不能来。
2．派对的整体快乐值是所有到场员工快乐值的累加。
3．你的目标是让派对的整体快乐值尽量大。
给定一个头节点boss，请返回派对的最大快乐值。
【要求】
如果以boss为头节点的整棵树有N个节点，请做到时间复杂度为O(N)。
【难度】
尉 ★★☆☆
【解答】
假设以X为头节点的整棵树如图3-44所示。
X有a、b、c三个直接下级，a、b、c再往下一级的关系在图中已经省略。现在分析以X为头节点的整棵树，最大快乐值如何得到。情况只有两种，一种为X来的情况下，整棵树的最大快乐值，记为yes_X_max；另一种为X不来的情况下，整棵树的最大快乐值，记为no_X_max。下面分别进行分析。
yes_X_max。在X来的情况下，派对一定会累加X的快乐值，记为X_happy，同时在这种情况下，a、b、c都不能来。假设以a为头节点的整棵树，在a不来情况下的最大快乐值记为no_a_max；以b为头节点的整棵树，在b不来的情况下的最大快乐值记为no_b_max；以c为头节点的整棵树，在c不来情况下的最大快乐值记为no_c_max。那么yes_X_max的值如下：
yes_X_max = X_happy + no_a_max + no_b_max + no_c_max
no_X_max。在X不来的情况下，派对无法累加X的快乐值，同时在这种情况下，a、b、c谁来不来都可以。假设以a为头节点的整棵树，在a不来情况下的最大快乐值记为no_a_max，在a来情况下的最大快乐值记为yes_a_max；以b为头节点的整棵树，在b不来情况下的最大快乐值记为no_b_max，在b来情况下的最大快乐值记为yes_b_max；以c为头节点的整棵树，在c不来情况下的最大快乐值记为no_c_max，在c来情况下的最大快乐值记为yes_c_max。那么no_X_max的值如下：
no_X_max = Max { no_a_max, yes_a_max } + Max { no_b_max, yes_b_max} + Max{ no_c_max, yes_c_max}
也就是说，某一个下级节点来还是不来，要看这个下级节点来还是不来的两种情况下，哪一种获得的收益最多。
yes_X_max和no_X_max哪个大，哪个就是X为头节点的整棵树的最大快乐值。
上面的分析说明中，以X为头节点的整棵树，需要以直接下级为头节点的每一棵子树，都给出子树的头节点（a、b、c）来还是不来两种情况下的最大收益。整个过程明显是一个递归过程。递归过程的返回值结构如ReturnData类所示。
// 每棵树处理完之后的返回值类型
public class ReturnData {
public int yesHeadMax; // 树的头节点来的情况下，整棵树的最大收益
public int noHeadMax; // 树的头节点不来的情况下，整棵树的最大收益
public ReturnData(int yesHeadMax, int noHeadMax) {
this.yesHeadMax = yesHeadMax;
this.noHeadMax = noHeadMax;
}
}
整个递归过程如process方法所示。
// 该函数处理以X为头节点的树，并且返回X来和不来两种情况下的最大快乐值
// 所以返回值的类型为ReturnData类型
public static ReturnData process(Employee X) {
int yesX = X.happy;// X来的情况下，一定要累加上X自己的快乐值
int noX = 0;// X不来的情况下，不累加上X自己的快乐值
if (X.subordinates.isEmpty()) { // 如果X没有直接下属，说明是基层员工，直接返回即可
return new ReturnData(yesX, noX);
} else { // 如果X有直接下属，就按照题目的分析来
// 枚举X的每一个直接下级员工next
for (Employee next : X.subordinates) {
// 递归调用process，得到以next为头节点的子树，
//在next来和不来两种情况下分别获得的最大收益
ReturnData subTreeInfo = process(next);
yesX += subTreeInfo.noHeadMax; // 见书中yes_X_max的分析
noX += Math.max(subTreeInfo.yesHeadMax,
subTreeInfo.noHeadMax);// 见书中no_X_max的分析
}
return new ReturnData(yesX, noX);
}
} 理解了上面的分析之后，我们看以boss为头节点的整棵树的答案怎么得到。毫无疑问，以boss为头节点的整棵树分两种情况，boss来的情况下整棵树的最大快乐值和boss不来的情况下整棵树的最大快乐值，最大的那个就是我们想要的答案。整个解法的主方法请看如下的getMaxHappy方法。
public int getMaxHappy(Employee boss) {
ReturnData allTreeInfo = process(boss);
return Math.max(allTreeInfo.noHeadMax, allTreeInfo.yesHeadMax);
} 通过先序和中序数组生成后序数组
【题目】
已知一棵二叉树所有的节点值都不同，给定这棵树正确的先序和中序数组，不要重建整棵树，而是通过这两个数组直接生成正确的后序数组。
【难度】
士 ★☆☆☆
【解答】
举例说明生成后序数组的过程，假设pre=[1,2,4,5,3,6,7]，in=[4,2,5,1,6,3,7]。
1．根据pre和in的长度，生成长度为7的后序数组pos，按以下规则从右到左填满pos。
2．根据[1,2,4,5,3,6,7]和[4,2,5,1,6,3,7]，设置pos[6]=1，即先序数组最左边的值。根据1，把in划分成[4,2,5]和[6,3,7]，pre中1的右边部分根据这两部分等长划分出[2,4,5]和[3,6,7]。[2,4,5]和[4,2,5]一组，[3,6,7]和[6,3,7]一组。
3．根据[3,6,7]和[6,3,7]，设置pos[5]=3，再次划分出[6]（来自[3,6,7]）和[6]（来自[6,3,7]）一组，[7]（来自[3,6,7]）和[7]（来自[6,3,7]）一组。
4．根据[7]和[7]，设置pos[4]=7。
5．根据[6]和[6]，设置pos[3]=6。
6．根据[2,4,5]和[4,2,5]，设置pos[2]=2，再次划分出[4]（来自[2,4,5]）和[4]（来自[4,2,5]）一组，[5]（来自[[2,4,5]）和[5]（来自[4,2,5]）一组。
7．根据[5]和[5]，设置pos[1]=5。
8．根据[4]和[4]，设置pos[0]=4。
如上过程简单总结为：根据当前的先序和中序数组，设置后序数组最右边的值，然后划分出左子树的先序、中序数组，以及右子树的先序、中序数组，先根据右子树的划分设置好后序数组，再根据左子树的划分，从右边到左边依次设置好后序数组的全部位置。
具体过程请参看如下代码中的getPosArray方法。
public int[] getPosArray(int[] pre, int[] in) {
if (pre == null || in == null) {
return null;
}
int len = pre.length;
int[] pos = new int[len];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < len; i++) {
map.put(in[i], i);
}
setPos(pre, 0, len - 1, in, 0, len - 1, pos, len - 1, map);
return pos;
}
// 从右往左依次填好后序数组s
// si为后序数组s该填的位置
// 返回值为s该填的下一个位置
public int setPos(int[] p, int pi, int pj, int[] n, int ni, int nj,
int[] s, int si, HashMap<Integer, Integer> map) {
if (pi > pj) {
return si;
}
s[si--] = p[pi];
int i = map.get(p[pi]);
si = setPos(p, pj - nj + i + 1, pj, n, i + 1, nj, s, si, map);
return setPos(p, pi + 1, pi + i - ni, n, ni, i - 1, s, si, map);
} 统计和生成所有不同的二叉树
【题目】
给定一个整数N，如果N<1，代表空树结构，否则代表中序遍历的结果为{1,2,3,…，N}。请返回可能的二叉树结构有多少。
例如，N=-1时，代表空树结构，返回1；N=2时，满足中序遍历为{1, 2}的二叉树结构只有如图3-45所示的两种，所以返回结果为2。
进阶：N的含义不变，假设可能的二叉树结构有M种，请返回M个二叉树的头节点，每一棵二叉树代表一种可能的结构。
【难度】
尉 ★★☆☆
【解答】
如果中序遍历有序且无重复值，则二叉树必为搜索二叉树。假设num(a)代表a个节点的搜索二叉树有多少种可能，再假设序列为{1,…,i,…,N}，如果以1作为头节点，1不可能有左子树，故以1作为头节点有多少种可能的结构，完全取决于1的右子树有多少种可能结构，1的右子树有N-1个节点，所以有num(N-1)种可能。
如果以i作为头节点，i的左子树有i-1个节点，所以可能的结构有num(i-1)种，右子树有N-i个节点，所以有num(N-i)种可能。故以i为头节点的可能结构有num(i-1)´num(N-i)种。
如果以N作为头节点，N不可能有右子树，故以N作为头节点有多少种可能，完全取决于N的左子树有多少种可能，N的左子树有N-1个节点，所以有num(N-1)种。
把从1到N分别作为头节点时，所有可能的结构加起来就是答案，可以利用动态规划来加速计算的过程，从而做到O(N2)的时间复杂度。
具体请参看如下代码中的numTrees方法。
public int numTrees(int n) {
if (n < 2) {
return 1;
}
int[] num = new int[n + 1];
num[0] = 1;
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < i + 1; j++) {
num[i] += num[j - 1] * num[i - j];
}
}
return num[n];
}
进阶问题与原问题的过程其实很类似。如果要生成中序遍历是{a…b}的所有结构，就从a开始一直到b，枚举每一个值作为头节点，把每次生成的二叉树结构的头节点都保存下来即可。假设其中一次是以i值为头节点的（a≤i≤b），以i为头节点的所有结构按如下步骤生成。
1．用{a…i-1}递归生成左子树的所有结构，假设所有结构的头节点保存在listLeft链表中。
2．用{a…i+1}递归生成右子树的所有结构，假设所有结构的头节点保存在listRight链表中。
3．在以i为头节点的前提下，listLeft中的每一种结构都可以与listRight中的每一种结构构成单独的结构，且和其他任何结构都不同。为了保证所有的结构之间不互相交叉，所以对每一种结构都复制出新的树，并记录在总的链表res中。
具体过程请参看如下代码中的generateTrees方法。
public List<Node> generateTrees(int n) {
return generate(1, n);
}
public List<Node> generate(int start, int end) {
List<Node> res = new LinkedList<Node>();
if (start > end) {
res.add(null);
}
Node head = null;
for (int i = start; i < end + 1; i++) {
head = new Node(i);
List<Node> lSubs = generate(start, i - 1);
List<Node> rSubs = generate(i + 1, end);
for (Node l : lSubs) {
for (Node r : rSubs) {
head.left = l;
head.right = r;
res.add(cloneTree(head));
}
}
}
return res;
}
public Node cloneTree(Node head) {
if (head == null) {
return null;
}
Node res = new Node(head.value);
res.left = cloneTree(head.left);
res.right = cloneTree(head.right);
return res;
} 统计完全二叉树的节点数
【题目】
给定一棵完全二叉树的头节点head，返回这棵树的节点个数。
【要求】
如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。
【难度】
尉 ★★☆☆
【解答】
遍历整棵树当然可以求出节点数，但这肯定不是最优解法，本书不再详述。
如果完全二叉树的层数为h，本书的解法可以做到时间复杂度为O(h2)，具体过程如下：
1．如果head==null，说明是空树，直接返回0。
2．如果不是空树，就求树的高度，求法是找到树的最左节点看能到哪一层，层数记为h。
3．这一步是求解的主要逻辑，也是一个递归过程，记为bs(node,l,h)，node表示当前节点，l表示node所在的层数，h表示整棵树的层数是始终不变的。bs(node,l,h)的返回值表示以node为头节点的完全二叉树的节点数是多少。初始时，node为头节点head，l为1，因为head在第1层，一共有h层始终不变。那么这个递归的过程可以用两个例子来说明，如图3-46和图3-47所示。
找到node右子树的最左节点，如果像图3-47的例子一样，发现它能到达最后一层，即h==4层。此时说明node的整棵左子树都是满二叉树，并且层数为h-l层，一棵层数为h-l的满二叉树，其节点数为2h-1-1个。如果加上node节点自己，那么节点数为2^(h-1)-1+1==2^(h-1)个。此时如果再知道node右子树的节点数，那么以node为头节点的完全二叉树上到底有多少个节点就求出来了。那么node右子树的节点数到底是多少呢？就是bs(node.right,l+1,h)的结果，递归去求即可。最后整体返回2^(h-1)+bs(node.right,l+1,h)。
找到node右子树的最左节点，如果像图3-47的例子一样，发现它没有到达最后一层，说明node的整棵右子树都是满二叉树，并且层数为h-l-1层，一棵层数为h-l-1的满二叉树，其节点数为2h-l-1-1个。如果加上node节点自己，那么节点数为2^(h-l-1)-1+1==2^(h-l-1)个。此时如果再知道node左子树的节点数，那么以node为头节点的完全二叉树上到底有多少个节点就求出来了。node左子树的节点数到底是多少呢？就是bs(node.left,l+1,h)的结果，递归去求即可，最后整体返回2^(h-l-1)+bs(node.left,l+1,h)。
全部过程请参看如下代码中的nodeNum方法。
public int nodeNum(Node head) {
if (head == null) {
return 0;
}
return bs(head, 1, mostLeftLevel(head, 1));
}
public int bs(Node node, int l, int h) {
if (l == h) {
return 1;
}
if (mostLeftLevel(node.right, l + 1) == h) {
return (1 << (h - l)) + bs(node.right, l + 1, h);
} else {
return (1 << (h - l - 1)) + bs(node.left, l + 1, h);
}
}
public int mostLeftLevel(Node node, int level) {
while (node != null) {
level++;
node = node.left;
}
return level - 1;
} 每一层只会选择一个节点node进行bs的递归过程，所以调用bs函数的次数为O(h)。每次调用bs函数时，都会查看node右子树的最左节点，所以会遍历O(h)个节点，整个过程的时间复杂度为O(h2)。
<p> 本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。 同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p> <p> <br /> </p>
投递英伟达等公司9个岗位