年輕即出發(fā)...
簡書：http://www.itdecent.cn/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源碼：https://github.com/zqtao2332
個人網(wǎng)站：http://www.zqtaotao.cn/ （停止維護(hù)更新內(nèi)容）
QQ交流群：606939954
? 咆哮怪獸一枚...嗷嗷嗷...趁你現(xiàn)在還有時間，盡你自己最大的努力。努力做成你最想做的那件事，成為你最想成為的那種人，過著你最想過的那種生活。也許我們始終都只是一個小人物，但這并不妨礙我們選擇用什么樣的方式活下去，這個世界永遠(yuǎn)比你想的要更精彩。
最后：喜歡編程，對生活充滿激情
本節(jié)內(nèi)容預(yù)告
2020秋招-360筆試題-尋宗問祖
2020秋招-360筆試題-尋宗問祖
尋祖問宗
時間限制：C/C++語言 1000MS；其他語言 3000MS
內(nèi)存限制：C/C++語言 65536KB；其他語言 589824KB
題目描述：
姓氏是人的符號標(biāo)志，是家族血脈的傳承；族譜是家族血脈傳承的文字記載。同姓的兩個中國人，根據(jù)族譜或許能夠查出上面幾代內(nèi)是同一個祖先。
查一下族譜，也許當(dāng)代某位同姓名人就是你的遠(yuǎn)房親戚，驚喜不驚喜，意外不意外！??！
360筆試題-尋宗問祖.png
輸入
二元查找樹（
1.若左子樹不空，左子樹值都小于父節(jié)點；
2.如右子樹不空，右子樹值都大于父節(jié)點；
3.左、右子樹都是二元查找樹；
4.沒有鍵值相等的節(jié)點）上任意兩個節(jié)點的值，請找出它們最近的公共祖先。
輸入三行行，第一行為樹層級，第二行為數(shù)節(jié)點（其中-1表示為空節(jié)點），第
三行為需要查找祖先的兩個數(shù)。
在例圖中（虛線框沒有真實節(jié)點，為了輸入方便對應(yīng)位置輸-1）查找12和20的最近公共祖先輸入為：
4
9 6 15 2 -1 12 25 -1 -1 -1 -1 -1 -1 20 37
12 20
輸出
輸出給出兩個數(shù)在樹上的最近公共祖先數(shù)值，如果沒有公共祖先，輸出-1；如果其中一個節(jié)點是另一個節(jié)點的祖先，
輸出這個祖先點（如例圖中找15、20最近公共祖先，輸出15）；如果輸入無效，輸出-1。
樣例輸入
4
9 6 15 2 -1 12 25 -1 -1 -1 -1 -1 -1 20 37
12 20
樣例輸出
15
package cn.zqtao.examintion;
import java.util.LinkedList;
import java.util.Queue;
/**
* 1、層次遍歷重建二叉樹
* 2、尋找二叉樹的最近祖先
*
* 尋祖問宗
* 時間限制：C/C++語言 1000MS；其他語言 3000MS
* 內(nèi)存限制：C/C++語言 65536KB；其他語言 589824KB
* 題目描述：
* 姓氏是人的符號標(biāo)志，是家族血脈的傳承；族譜是家族血脈傳承的文字記載。同姓的兩個中國人，根據(jù)族譜或許能夠查出上面幾代內(nèi)是同一個祖先。
* 查一下族譜，也許當(dāng)代某位同姓名人就是你的遠(yuǎn)房親戚，驚喜不驚喜，意外不意外！??！
*
* 輸入
* 二元查找樹（
* 1.若左子樹不空，左子樹值都小于父節(jié)點；
* 2.如右子樹不空，右子樹值都大于父節(jié)點；
* 3.左、右子樹都是二元查找樹；
* 4. 沒有鍵值相等的節(jié)點）上任意兩個節(jié)點的值，請找出它們最近的公共祖先。
* 輸入三行行，第一行為樹層級，第二行為數(shù)節(jié)點（其中-1表示為空節(jié)點），第
* 三行為需要查找祖先的兩個數(shù)。
* 在例圖中（虛線框沒有真實節(jié)點，為了輸入方便對應(yīng)位置輸-1）查找12和20的最近公共祖先輸入為：
* 4
* 9 6 15 2 -1 12 25 -1 -1 -1 -1 -1 -1 20 37
* 12 20
* 輸出
* 輸出給出兩個數(shù)在樹上的最近公共祖先數(shù)值，如果沒有公共祖先，輸出-1；如果其中一個節(jié)點是另一個節(jié)點的祖先，
* 輸出這個祖先點（如例圖中找15、20最近公共祖先，輸出15）；如果輸入無效，輸出-1。
*
* 樣例輸入
* 4
* 9 6 15 2 -1 12 25 -1 -1 -1 -1 -1 -1 20 37
* 12 20
* 樣例輸出
* 15
*/
public class Code_05_RebuildBTreeByLevel_And_FindLowestCommonAncestor {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
/**
* 根據(jù)層次遍歷重建二叉樹
*/
public static Node creatBinTree(int[] arr) {
LinkedList<Node> list = new LinkedList<>();
for (int i = 0; i < arr.length; i++) {
list.add(arr[i] == -1 ? null : new Node(arr[i]));
}
Node head = list.get(0);
for (int i = 0; i < arr.length / 2 - 1; i++) {
if (list.get(i) != null) {
list.get(i).left = list.get(i * 2 + 1);
list.get(i).right = list.get(i * 2 + 2);
}
}
int i = arr.length / 2 - 1;
list.get(i).left = list.get(i * 2 + 1);
if (arr.length % 2 == 1) {
list.get(i).right = list.get(i * 2 + 2);
}
return head;
}
/**
* 層次遍歷二叉樹
* 隊列實現(xiàn)
*/
public static void levelTraverse(Node node) {
if (node == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(node);
while (!queue.isEmpty()) {
Node tmp = queue.poll();
System.out.print(tmp.value + " ");
if (tmp.left != null) queue.add(tmp.left);
if (tmp.right != null) queue.add(tmp.right);
}
}
/**
* 二叉樹尋找最近祖先
* @param head
* @param o1
* @param o2
* @return
*/
public static Node lowestAncestor(Node head, Node o1, Node o2) {
if (head == null || head.value == o1.value || head.value == o2.value)
return head;
Node left = lowestAncestor(head.left, o1, o2);
Node right = lowestAncestor(head.right, o1, o2);
if (left != null && right != null)
return head;
return left != null ? left : right;
}
public static void main(String[] args) {
// for test ：層次遍歷重建二叉樹
int[] arr = {9, 6, 15, 2, -1, 12, 25, -1, -1, -1, -1, -1, -1, 20, 37};
Node node = creatBinTree(arr);
printTree(node);
levelTraverse(node);
System.out.println();
// for test : 二叉樹尋找最近祖先
int[] arr2 = {1,2,3,4,5,6,7};
Node node2 = creatBinTree(arr2);
System.out.println(node2.value);
printTree(node2);
Node node1 = lowestAncestor(creatBinTree(arr2), new Node(4), new Node(6));
System.out.println(node1.value);
}
}
