[IT 필기시험 면접 문제 정리] 두 갈래 나무 두 노드를 찾는 최근의 공공조상.
16888 단어 면접 문제
두 갈래 나무의 임의의 두 노드를 구하는 최근의 공공 조상들도 LCA 문제(Lowest Common Ancestor)라고 부른다.
두 갈래 찾기 트리
만약 이 두 갈래 나무가 두 갈래 찾기 나무라면, LCA를 구하는 것은 매우 간단하다.
기본 사상은 나무 뿌리부터 시작하여 이 노드의 값은 t이다. 만약에 t가 t1과 t2보다 크면 t1과 t2가 모두 t의 왼쪽에 있기 때문에 그들의 공동 조상은 반드시 t의 왼쪽 나무에서 t.left부터 검색해야 한다.만약 t가 t1과 t2보다 작다면 t1과 t2가 모두 t의 오른쪽에 있다는 것을 설명한다. 그러면 t.right부터 검색한다.만약에 t1
[참조 코드]
1 public int query(Node t1, Node t2, Node t) {
2 int left = t1.value;
3 int right = t2.value;
4 Node parent = null;
5
6 if (left > right) {
7 int temp = left;
8 left = right;
9 right = temp;
10 }
11
12 while (true) {
13 if (t.value < left) {
14 parent = t;
15 t = t.right;
16 } else if (t.value > right) {
17 parent = t;
18 t = t.left;
19 } else if (t.value == left || t.value == right) {
20 return parent.value;
21 } else {
22 return t.value;
23 }
24 }
25 }일반 두 갈래 나무
알고리즘 사상: 만약에 한 노드의 왼쪽 트리가 p, q의 한 노드를 포함하고 오른쪽 트리가 다른 노드를 포함한다면 이 노드는 p, q의 최근 공공 조상이다.
[참조 코드]
해법 1:
1 public static Node findNCA(Node root, Node p, Node q)
2 {
3 if (isintree(root.left, p) && isintree(root.left, q))
4 return findNCA(root.left, p, q);
5 if (isintree(root.right, p) && isintree(root.right, q))
6 return findNCA(root.right, p, q);
7 return root;
8 }
9
10 public static boolean isintree(Node root, Node node)
11 {
12 if (root == null)
13 return false;
14 if (root == node)
15 return true;
16 return isintree(root.left, node) || isintree(root.right, node);
17 }해법 2:
1 static int TWO_NODES_FOUND = 2;
2 static int ONE_NODES_FOUND = 1;
3 static int NO_NODES_FOUND = 0;
4
5 public static int covers(Node root, Node p, Node q)
6 {
7 int ret = NO_NODES_FOUND;
8 if (root == null)
9 return ret;
10 if (root == p || root == q)
11 ret += 1;
12 ret += covers(root.left, p, q);
13 if (ret == TWO_NODES_FOUND)
14 return ret;
15 return ret + covers(root.right, p, q);
16 }
17
18 private static Node findNCA(Node root, Node p, Node q)
19 {
20 if (q == p && (root.left == q || root.right == q))
21 return root;
22 int nodesFromLeft = covers(root.left, p, q);
23 if (nodesFromLeft == TWO_NODES_FOUND)
24 {
25 if (root.left == p || root.left == q)
26 return root.left;
27 else
28 return findNCA(root.left, p, q);
29 } else if (nodesFromLeft == ONE_NODES_FOUND)
30 {
31 if (root == p)
32 return p;
33 else if (root == q)
34 return q;
35 }
36
37 int nodesFromRight = covers(root.right, p, q);
38 if (nodesFromRight == TWO_NODES_FOUND)
39 {
40 if (root.right == p || root.right == q)
41 return root.right;
42 else
43 return findNCA(root.right, p, q);
44 } else if (nodesFromRight == ONE_NODES_FOUND)
45 {
46 if (root == p)
47 return p;
48 else if (root == q)
49 return q;
50 }
51
52 if (nodesFromLeft == ONE_NODES_FOUND
53 && nodesFromLeft == ONE_NODES_FOUND)
54 return root;
55 else
56 return null;
57 }해법 3: 인터넷 버전:
1 public static int FindNCA(Node root, Node a, Node b, Node out)
2 {
3 if (root == null)
4 return 0;
5 if (root == a || root == b)
6 return 1;
7
8 int iLeft = FindNCA(root.left, a, b, out);
9 if (iLeft == 2)
10 return 2;
11
12 int iRight = FindNCA(root.right, a, b, out);
13 if (iRight == 2)
14 return 2;
15
16 if (iLeft + iRight == 2)
17 out = root;
18
19 return iLeft + iRight;
20 }이 인터넷에서는 출력할 때 2시가 되어야 출력한다고 하지만 2시가 되면 그 중 하나가 다른 아버지 노드의 상황이라면 판단할 수 없다.따라서 이론적으로는 반환 결과가 0보다 크면 결과를 출력할 수 있다고 고쳐야 한다.그러나 정확성은 그다지 확실하지 않고 절차가 정확해야 한다.
참조:
http://blog.csdn.net/w397090770/article/details/7615447
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 프로그래머 면접에서의 다중 스레드 문제 요약wait ()/notify ()/notify All () 의 모든 방법을 호출할 때, 현재 라인이 이 대상의 자물쇠를 얻지 못하면, Illegal MonitorState Exception의 이상을 던집니다. Thre...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
