나뭇잎에서 루트까지 이진 트리를 만드는 방법

Question

나뭇잎에서 루트까지 이진 트리를 만드는 방법은 반대 방향입니다.

x01 = x0 xor x1, x23 = x2 xor x3, x45 = x4 xor x5 <=> **x01**x23**x45**

:이 알고리즘은 우리가 얻을 적용 xo = 44, x1 = 333, x2 = 55, x3 = 555, x4 = 4, x5 = 333 <=> **x0**x1**x2**x3**x4**x5,

하자 나는,이 암호화를 적용 스트링과 XOR의 압축 알고리즘을 쓰고 있어요 예를 들어 우리는 원래 **44**333**55**555**4**333** 같은 문자열,

이 다시,

x= x01 xor x23 and x= xxor x23.

이 구조는 이진 트리에서 유지하기 쉽지만 이진 트리의 방향으로는 역방향을 만드는 방법입니다.

Answer 1

한 가지 가능한 솔루션이

1. 모든 주어진 값의 TreeNode를 확인하고 큐에 넣어 수 있습니다.
2. 대기열 이름의 첫 번째 요소를 첫 번째로 팝합니다. 2.1 큐에서 다음 요소를 팝하고 SECOND로 이름을 지정하십시오. 존재하지 않으면 휴식. 2.2 노드 TEMP treenode를 만듭니다 (이것은 FIRST와 SECOND의 XOR입니다). 2.3 FIRST 및 SECOND를 TEMP의 자식으로 만듭니다. 2.4 TEMP를 대기열로 밀어 넣습니다. 2.5 큐가 하나의 요소 만 가질 때까지 2에서 2 단계를 반복합니다.
3. 먼저 루트로 표시하십시오.

Answer 2

이 목적으로 간단한 std :: vector를 쉽게 사용할 수 있습니다. heaport에 힙이 어떻게 만들어지고 있는지를 생각해 보면 구조를 쉽게 파악할 수 있습니다. 이것은 실제로 원래 힙이 아니지만이 종류의 이진 트리 표현은 매우 유용 할 수 있습니다.

그래서, 오히려 표준 : 벡터를 사용하여 "역"힙 형태의 최종 구조를 나타내는 것이다 : {44, 333, 55, 555, 4, 333 : 초기 벡터는 N = 6 개 요소 것이다 을 }

다음 단계는 n-1 = 5 연산을 만들고 {44, 333, 55, 555, 4, 333, 44333, 33355, 55555, 5554, 4333과 같은 벡터의 끝에 합을 더합니다. }

다음 단계 꼬리 요소 (4) 조작 : {44, 333, 55, 555, 4, 333, 44,333, 33,355, 55,555, 5,554, 4,333, 4433333355, 3335555555, 555,555,554, 55,544,333}

그래서, (n-1) + (n-2) + (n-3) + ... + 1 = (n-1) * n/2 작업을 수행하면 트리가 역순으로됩니다.

오른쪽에서 왼쪽으로 이동하면 트리를 BFS 순서로 트래버스합니다.