二元查找樹（1.若左子樹不空，左子樹值都小于父節(jié)點；2.如右子樹不空，右子樹值都大于父節(jié)點；3.左、右子樹都是二元查找樹；4. 沒有鍵值相等的節(jié)點）上任意兩個節(jié)點的值，請找出它們最近的公共祖先。

輸入

三行，第一行為樹層級，第二行為數節(jié)點（其中-1表示為空節(jié)點），第三行為需要查找祖先的兩個數。

在例圖中（虛線框沒有真實節(jié)點，為了輸入方便對應位置輸-1）查找12和20的最近公共祖先輸入為：

4

9 6 15 2 -1 12 25 -1 -1 -1 -1 -1 -1 20 37

12 20

輸出

輸出給出兩個數在樹上的最近公共祖先數值，如果沒有公共祖先，輸出-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

?解題代碼

import java.util.Scanner; import java.util.Stack;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int high = in.nextInt();if (high == 0) {System.out.println(-1);return;}int numOfNode = (int) (Math.pow(2, high) - 1);int[] tree = new int[numOfNode + 1];for (int i = 1; i <= numOfNode; i++) {tree[i] = in.nextInt();}int n1 = in.nextInt();int n2 = in.nextInt();int index1 = 0;int index2 = 0;int count = 0;for (int i = 1; i <= numOfNode; i++) {if (n1 == tree[i]) {index1 = i;count++;}if (n2 == tree[i]) {index2 = i;count++;}}if (count != 2) {System.out.println(-1);return;}Stack<Integer> stack1 = getPath(index1, tree);Stack<Integer> stack2 = getPath(index2, tree);int res = -1;while (!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek().equals(stack2.peek())) {res = stack1.pop();stack2.pop();}System.out.println(res);}private static Stack<Integer> getPath(int index, int[] tree) {Stack<Integer> stack = new Stack<>();while (index / 2 != 0) {stack.push(tree[index]);index = index / 2;}stack.push(tree[1]);return stack;} }

?

總結

以上是生活随笔為你收集整理的2020年奇安信校招JAVA岗笔试的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。