腾讯实习生笔试编程题--满二叉排序树，给定三个结点，求公共父结点

今年（2017）腾讯暑期实习生招聘笔试感觉好难，题目分两个部分总共2个小时，第一部分是30道不定项选择题，第二部分包含2道简答题和2道编程题，
第一道编程题做了一半，没完全写出来，现在有时间总结一下：
题目：一颗满二叉排序树，节点值范围为：1~2^(N-1),给定三个子节点，求最大的公共父节点；
如输入层数N=4，子节点11,13,15; 则输出:12

分析

解决这道题的关键，主要是要清晰的知道二叉排序树的性质：左节点的值小于父节点的值，右节点值大于父节点的值。
当N=4时，共有15个节点对应的满二叉排序树为（可利用二分法从上到下建立二叉排序树）：
;
可以知道有以下性质：

1. 以8为根节点，在左子树中一直往右走，可以找到左子树的最大值7，比根节点小1；
2. 右子树一直往左走，可以找到右子树的最小值9，比根节点大1；
3. 根节点的值是最左端的值和最右端的值之和的一半。

我们可以这样找最大的公共父结点（可以用分治法）：

1. 如果输入的结点在根结点的两边，则最大公共父结点必然是根结点，直接返回根结点；
2. 如果输入的结点都在根结点的左边，往左子树遍历，更新根结点的值，利用性质1 & 3，得到新树的最右结点及根结点的值；
3. 如果输入的结点都在根结点的右边，往右子树遍历，更新根结点的值，利用性质2 & 3，得到新树的最左结点及根结点的值；
4. 重复2.3步骤，直到出现1情况，结束。

实现代码

实现方法1是实现题目要求的，只输入层数N和3个子结点值，得到最大公共父结点；
实现方法2是扩展的，具有更好的通用性，输入层数N、子结点个数n及子结点的值，得到最大公共父结点。

实现方法1

public class  Main{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		while (in.hasNextInt()) {
			// 树的高度
			int k = in.nextInt();

			// 最开始根节点的值
			int root = (int) Math.pow(2, k) / 2;

			// 最开始的最左叶子节点和最右叶子节点
			int leftNode = 1;
			int rightNode = (int) Math.pow(2, k) - 1;

			// 输入任意3叶子节点的值
			int node1 = in.nextInt();
			int node2 = in.nextInt();
			int node3 = in.nextInt();

			for (int i = 1; i <= k; i++) {
				// 3个叶子节点全在根节点的左部,更新最右节点和根节点
				if (node1 < root && node2 < root && node3 < root) {
					rightNode = root - 1;
					root = (leftNode + rightNode) / 2;
				}

				// 3个叶子节点全在根节点的右部,更新最左节点和根节点
				else if (node1 > root && node2 > root && node3 > root) {
					leftNode = root + 1;
					root = (leftNode + rightNode) / 2;
				}

				// 一大一小的情形下根节点即为最大公共父节点
				else {
					System.out.println(root);
					break;
				}

			}

		}
	}
}

实现方法2

/**
 * 改进版，输入层数N，节点数n，个数范围为：2-2^-1
 * 输出二叉排序树的公共父节点
 *
 */

public class Main{

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		while (in.hasNextInt()) {
			// 树的高度
			int N = in.nextInt();

			// 最开始根节点的值
			int root = (int) Math.pow(2, N) / 2;

			// 最开始的最左叶子节点和最右叶子节点
			int leftNode = 1;
			int rightNode = (int) Math.pow(2, N) - 1;

			// 输入任意n叶子节点的值
			int n = in.nextInt();
			int[] arrNodes = new int[n];
			for (int i = 0; i < arrNodes.length; i++) {
				arrNodes[i] = in.nextInt();
			}

			// 从上到下按层次遍历N层
			for (int i = 1; i <= N; i++) {
				int count = 0;
				for (int j = 0; j < n; j++) {

					// 都在左边，count+1；
					if (arrNodes[j] < root) {
						count += 1;
					}

					// 都在右边，count+2
					else if (arrNodes[j] > root) {
						count += 2;
					}

					// 其中有一个是根节点
					else {
						count += 0;
					}

				}

				/**
				 * count的值n或者2n或者两者之间，
				 * n代表都在左边，更新最右节点和根节点
				 * 2n代表都在右边，更新最左节点和根节点
				 * 两者之间代表，分布在根节点两边，直接返回根节点
				 */
				if (count == n) {
					rightNode = root - 1;
					root = (leftNode + rightNode) / 2;
				} else if (count == 2 * n) {

					leftNode = root + 1;
					root = (leftNode + rightNode) / 2;

				} else {
					System.out.println(root);
					break;
				}

			}

		}
		in.close();
	}
}

测试结果

参考博文

1. f91og的博客