[IT 필기시험 면접 문제 정리] 두 갈래 나무의 순서와 중간 순서를 정하고 두 갈래 나무의 귀속 알고리즘을 구축한다.
4771 단어 면접 문제
그 선순위 서열의 첫 번째 요소는 루트 노드이고, 그 다음은 왼쪽 트리의 선순위 서열이며, 그 다음은 오른쪽 트리의 선순위 서열이며, 고체 루트 노드는 선순위 서열에서 분리될 수 있다.중차 서열에서 확정된 루트 노드를 찾습니다. 중차 서열 특성에 따라 수건 서열에서 루트 노드 앞의 서열은 왼쪽 트리의 중차 서열이고 루트 노드 뒤의 서열은 오른쪽 트리의 중차 서열입니다.좌우 트리의 중차 서열 길이로 이 트리의 선차 서열에서 좌우 트리의 선차 서열의 경계점을 찾아 두 갈래 트리의 좌우 트리의 선차 서열을 얻을 수 있다.
귀속 실현: 귀속 함수 입력: 두 갈래 트리의 선순 서열과 중순 서열;-, 세워진 두 갈래 나무의 뿌리 노드를 되돌려줍니다.알고리즘 사상: 1) 두 갈래 나무가 비어 있으면 되돌아온다.2) 비어 있지 않으면 첫 번째 원소를 순서대로 취하여 루트 노드를 만듭니다.3) 중간 시퀀스에서 루트 노드를 찾아 좌우 하위 트리의 우선 시퀀스와 중간 시퀀스를 확인합니다.4) 자신을 차례로 호출하여 왼쪽 나무를 짓는다.5) 자신을 차례로 호출하여 오른쪽 나무를 만든다.
[참조 코드]
1 public static TreeNode createBT(String pres, String ins)
2 {
3 int inpos = 0;
4 TreeNode root;
5 String leftPres, leftIns, rightPres, rightIns;
6
7 if (pres.length() == 0 || ins.length() == 0)
8 return null;
9 else
10 {
11 root = new TreeNode(pres.charAt(0));
12 while (ins.charAt(inpos) != root.value)
13 inpos++;
14 leftPres = pres.substring(1, inpos + 1);
15 leftIns = ins.substring(0, inpos);
16
17 root.left = createBT(leftPres, leftIns);
18 rightPres = pres.substring(inpos + 1, pres.length());
19 rightIns = ins.substring(inpos + 1, ins.length());
20 root.right = createBT(rightPres, rightIns);
21 }
22 return root;
23 }
24
25 class TreeNode
26 {
27 public char value;
28 public TreeNode left;
29 public TreeNode right;
30
31 public TreeNode(char value)
32 {
33 this.value = value;
34 }
35 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.