第三章：二叉树问题（五）
判断t1树是否包含t2树全部的拓扑结构
【题目】
给定彼此独立的两棵树头节点分别为t1和t2，判断t1树是否包含t2树全部的拓扑结构。
例如，如图3-34所示的t1树和如图3-35所示的t2树。
t1树包含t2树全部的拓扑结构，所以返回true。
【难度】
士 ★☆☆☆
【解答】
如果t1中某棵子树头节点的值与t2头节点的值一样，则从这两个头节点开始匹配，匹配的每一步都让t1上的节点跟着t2上的节点的先序遍历移动，每移动一步，都检查t1的当前节点是否与t2当前节点的值一样。比如，题目中的例子，t1中的节点2与t2中的节点2匹配，然后t1跟着t2向左，发现t1中的节点4与t2中的节点4匹配，t1跟着t2继续向左，发现t1中的节点8与t2中的节点8匹配，此时t2回到t2中的节点2，t1也回到t1中的节点2，然后t1跟着t2向右，发现t1中的节点5与t2中的节点5匹配。t2匹配完毕，结果返回true。如果匹配的过程中发现有不匹配的情况，则直接返回false，说明t1的当前子树从头节点开始，无法与t2匹配，那么再去寻找t1的下一棵子树。t1的每棵子树上都有可能匹配出t2，所以都要检查一遍。
因此，如果t1的节点数为N，t2的节点数为M，则该方法的时间复杂度为O(N´M)。
具体过程请参看如下代码中的contains方法，
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean contains(Node t1, Node t2) {
if (t2 == null) {
return true;
}
if (t1 == null) {
return false;
}
return check(t1, t2) || contains(t1.left, t2) || contains(t1.right, t2);
}
public boolean check(Node h, Node t2) {
if (t2 == null) {
return true;
}
if (h == null || h.value != t2.value) {
return false;
}
return check(h.left, t2.left) && check(h.right, t2.right);
} 判断t1树中是否有与t2树拓扑结构完全相同的子树
【题目】
给定彼此独立的两棵树头节点分别为t1和t2，判断t1中是否有与t2树拓扑结构完全相同的子树。
例如，如图3-36所示的t1树和如图3-37所示的t2树。
t1树有与t2树拓扑结构完全相同的子树，所以返回true。但如果t1树和t2树分别如图3-38和图3-39所示，则t1树就没有与t2树拓扑结构完全相同的子树，所以返回false。
【难度】
校 ★★★☆
【解答】
如果t1的节点数为N，t2的节点数为M，则本题最优解是时间复杂度为O(N+M)的方法。首先简单介绍一个时间复杂度为O(N´M)的方法，对于t1的每棵子树，都去判断是否与t2树的拓扑结构完全一样，这个过程的时间复杂度为O(M)，t1的子树一共有N棵，所以时间复杂度为O(N´M)，这种方法在本书中不再详述。
下面重点介绍一下时间复杂度为O(N+M)的方法，首先把t1树和t2树按照先序遍历的方式序列化，关于这个内容，请阅读本书“二叉树的序列化和反序列化”问题。以题目的例子来说，t1树序列化后的结果为“1!2!4!#!8!#!#!5!9!#!#!#!3!6!#!#!7!#!#!”，记为t1Str。t2树序列化后的结果为“2!4!#!8!#!#!5!9!#!#!#!”，记为t2Str。接下来，只要验证t2Str是否是t1Str的子串即可，这个用KMP算法可以在线性时间内解决。因此，t1序列化的过程为O(N)，t2序列化的过程为O(M)，KMP解决t1Str和t2Str的匹配问题O(M+N)，所以时间复杂度为O(M+N)。有关KMP算法的内容，请读者阅读本书“KMP算法”问题，关于这个算法非常清晰的解释，这里不再详述。
本题最优解的全部过程请参看如下代码中的isSubtree方法。
public boolean isSubtree(Node t1, Node t2) {
String t1Str = serialByPre(t1);
String t2Str = serialByPre(t2);
return getIndexOf(t1Str, t2Str) != -1;
}
public String serialByPre(Node head) {
if (head == null) {
return "#!";
}
String res = head.value + "!";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
// KMP
public int getIndexOf(String s, String m) {
if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
return -1;
}
char[] ss = s.toCharArray();
char[] ms = m.toCharArray();
int si = 0;
int mi = 0;
int[] next = getNextArray(ms);
while (si < ss.length && mi < ms.length) {
if (ss[si] == ms[mi]) {
si++;
mi++;
} else if (next[mi] == -1) {
si++;
} else {
mi = next[mi];
}
}
return mi == ms.length ? si - mi : -1;
}
public int[] getNextArray(char[] ms) {
if (ms.length == 1) {
return new int[] { -1 };
}
int[] next = new int[ms.length];
next[0] = -1;
next[1] = 0;
int pos = 2;
int cn = 0;
while (pos < next.length) {
if (ms[pos - 1] == ms[cn]) {
next[pos++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[pos++] = 0;
}
}
return next;
} 判断二叉树是否为平衡二叉树
【题目】
平衡二叉树的性质为：要么是一棵空树，要么任何一个节点的左右子树高度差的绝对值不超过1。给定一棵二叉树的头节点head，判断这棵二叉树是否为平衡二叉树。
【要求】
如果二叉树的节点数为N，则要求时间复杂度为O(N)。
【难度】
士 ★☆☆☆
【解答】
平衡二叉树的标准是：对任何子树来说，左子树和右子树的高度差都不超过1。本题解法的整体过程为树形dp套路，请读者先阅读本书“找到二叉树中的最大搜索二叉子树”问题了解这个套路，本题是这个套路的再次展示。
首先，树形dp套路的前提是满足的。依次考查每个节点为头节点的子树，如果都是平衡二叉树，那么整体就是平衡二叉树。
树形dp套路第一步：以某个节点X为头节点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性的。
可能性一：如果X的左子树不是平衡的，则以X为头节点的树就是不平衡的。
可能性二：如果X的右子树不是平衡的，则以X为头节点的树就是不平衡的。
可能性三：如果X的左子树和右子树高度差超过1，则以X为头节点的树就是不平衡的。
可能性四：如果上面可能性都没中，那么以X为头节点的树是平衡的。
树形dp套路第二步：根据第一步的可能性分析，列出所有需要的信息。左子树和右子树都需要知道各自是否平衡，以及高度这两个信息。
树形dp套路第三步：根据第二步信息汇总。定义信息如ReturnType类所示。
public class ReturnType {
public boolean isBalanced;
public int height;
public ReturnType(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
} 树形dp套路第四步：设计递归函数。递归函数是处理以X为头节点的情况下的***括设计递归的base case，默认直接得到左树和右树所有的信息，以及把可能性做整合，并且也返回第三步的信息结构这四个小步骤。本题的递归实现请看以下的process方法，主函数是以下的isBalanced方法。
public ReturnType process(Node head) {
if (head == null) {
return new ReturnType(true, 0);
}
ReturnType leftData = process(head.left);
ReturnType rightData = process(head.right);
int height = Math.max(leftData.height, rightData.height) + 1;
boolean isBalanced = leftData.isBalanced && rightData.isBalanced
&& Math.abs(leftData.height - rightData.height) < 2;
return new ReturnType(isBalanced, height);
}
public boolean isBalanced(Node head) {
return process(head).isBalanced;
}
根据后序数组重建搜索二叉树
【题目】
给定一个整型数组arr，已知其中没有重复值，判断arr是否可能是节点值类型为整型的搜索二叉树后序遍历的结果。
进阶问题：如果整型数组arr中没有重复值，且已知是一棵搜索二叉树的后序遍历结果，通过数组arr重构二叉树。
【难度】
士 ★☆☆☆
【解答】
原问题的解法。二叉树的后序遍历为先左、再右、最后根的顺序，所以，如果一个数组是二叉树后序遍历的结果，那么头节点的值一定会是数组的最后一个元素。根据搜索二叉树的性质，比后序数组最后一个元素值小的数组会在数组的左边，比数组最后一个元素值大的数组会在数组的右边。比如，arr=[2,1,3,6,5,7,4]，比4小的部分为[2,1,3]，比4大的部分为[6,5,7]。如果不满足这种情况，则说明这个数组一定不可能是搜索二叉树后序遍历的结果。接下来，数组划分成左边数组和右边数组，相当于二叉树分出了左子树和右子树，只要递归地进行如上判断即可。
具体过程请参看如下代码中的isPostArray方法。
public boolean isPostArray(int[] arr) {
if (arr == null || arr.length == 0) {
return false;
}
return isPost(arr, 0, arr.length - 1);
}
public boolean isPost(int[] arr, int start, int end) {
if (start == end) {
return true;
}
int less = -1;
int more = end;
for (int i = start; i < end; i++) {
if (arr[end] > arr[i]) {
less = i;
} else {
more = more == end ? i : more;
}
}
if (less == -1 || more == end) {
return isPost(arr, start, end - 1);
}
if (less != more - 1) {
return false;
}
return isPost(arr, start, less) && isPost(arr, more, end - 1);
} 进阶问题的分析与原问题同理，一棵树的后序数组中最后一个值为二叉树头节点的值，数组左部分都比头节点的值小，用来生成头节点的左子树，剩下的部分用来生成右子树。
具体过程请参看如下代码中的posArrayToBST方法。
public class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
public Node posArrayToBST(int[] posArr) {
if (posArr == null) {
return null;
}
return posToBST(posArr, 0, posArr.length - 1);
}
public Node posToBST(int[] posArr, int start, int end) {
if (start > end) {
return null;
}
Node head = new Node(posArr[end]);
int less = -1;
int more = end;
for (int i = start; i < end; i++) {
if (posArr[end] > posArr[i]) {
less = i;
} else {
more = more == end ? i : more;
}
}
head.left = posToBST(posArr, start, less);
head.right = posToBST(posArr, more, end - 1);
return head;
}
判断一棵二叉树是否为搜索二叉树和完全二叉树
【题目】
给定二叉树的一个头节点head，已知其中没有重复值的节点，实现两个函数分别判断这棵二叉树是否为搜索二叉树和完全二叉树。
【难度】
士 ★☆☆☆
【解答】
判断一棵二叉树是否为搜索二叉树，只要改写一个二叉树中序遍历，在遍历的过程中看节点值是否都是递增的即可。本书改写的是Morris中序遍历，所以时间复杂度为O(N)，额外空间复杂度为O(1)。有关Morris中序遍历的介绍，请读者阅读本书“遍历二叉树的神级方法”问题。需要注意的是，Morris遍历分调整二叉树结构和恢复二叉树结构两个阶段。因此，当发现节点值是降序时，不能直接返回false，这么做可能会跳过恢复阶段，从而破坏二叉树的结构。
通过改写Morris中序遍历来判断搜索二叉树的过程请参看如下代码中的isBST方法。
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public boolean isBST(Node head) {
if (head == null) {
return true;
}
boolean res = true;
Node pre = null;
Node cur1 = head;
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;
}
}
if (pre != null && pre.value > cur1.value) {
res = false;
}
pre = cur1;
cur1 = cur1.right;
}
return res;
} 判断一棵二叉树是否为完全二叉树，依据以下标准会使判断过程变得简单且易实现。
1．按层遍历二叉树，从每层的左边向右边依次遍历所有的节点。
2．如果当前节点有右孩子节点，但没有左孩子节点，则直接返回false。
3．如果当前节点并不是左右孩子节点全有，那么之后的节点必须都为叶节点，否则返回false。
4．遍历过程中如果不返回false，则遍历结束后返回true。
判断是否是完全二叉树的全部过程请参看如下代码中的isCBT方法。
public boolean isCBT(Node head) {
if (head == null) {
return true;
}
Queue<Node> queue = new LinkedList<Node>();
boolean leaf = false;
Node l = null;
Node r = null;
queue.offer(head);
while (!queue.isEmpty()) {
head = queue.poll();
l = head.left;
r = head.right;
if ((leaf&&(l!=null||r!=null)) || (l==null&&r!=null)) {
return false;
}
if (l != null) {
queue.offer(l);
}
if (r != null) {
queue.offer(r);
} else {
leaf = true;
}
}
return true;
} 通过有序数组生成平衡搜索二叉树
【题目】
给定一个有序数组sortArr，已知其中没有重复值，用这个有序数组生成一棵平衡搜索二叉树，并且该搜索二叉树中序遍历的结果与sortArr一致。
【难度】
士 ★☆☆☆
【解答】
本题的递归过程比较简单，用有序数组中最中间的数生成搜索二叉树的头节点，然后用这个数左边的数生成左子树，用右边的数生成右子树即可。
全部过程请参看如下代码中的generateTree方法。
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public Node generateTree(int[] sortArr) {
if (sortArr == null) {
return null;
}
return generate(sortArr, 0, sortArr.length - 1);
}
public Node generate(int[] sortArr, int start, int end) {
if (start > end) {
return null;
}
int mid = (start + end) / 2;
Node head = new Node(sortArr[mid]);
head.left = generate(sortArr, start, mid - 1);
head.right = generate(sortArr, mid + 1, end);
return head;
} <p> 本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。 同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p> <p> <br /> </p>
美团成长空间 1550人发布
查看11道真题和解析