左程云

2019-12-30 15:37 University of Chicago Java

关注

第三章：二叉树问题（五）

判断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;
	}

程序员代码面试指南文章被收录于专栏

本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~