특수 속성을 가진 이진 트리

Question

모든 내부 노드가 val = 'N'이고 모든 잎의 val = 'L'인 특수 속성을 가진 이진 트리가 있습니다. 그 선주문을 감안할 때. 트리를 구성하고 루트 노드를 리턴하십시오.

모든 노드 중 하나를 두 아이 또는 자식

Answer 1

그냥 기본 개념을 가질 수있다 : 머리가 "현재"노드입니다 스택을 유지하고 순차적으로 선주문을 나타내는 문자열을 읽습니다.

이제 'L'을 만나면 "현재"노드가 자식으로 잎을 가짐을 의미하므로 올바른 하위 노드로 "전환"하고 해당 하위 트리를 다시 시작하고 그 하위 트리; 'L'을 만나면 "현재 노드"에 이미 두 개의 자식이있는 경우 스택의 요소를 팝합니다.

Answer 2

재귀는 친구입니다.

재귀 적 방법으로 보면 다른 것을 어떻게하는지 쉽게 알 수 있습니다.

예를 들어 InOrder 순회를 인쇄하고 싶다고 가정 해 보겠습니다. 코드는 다음과 같이 표시됩니다

void PrintInorderFromPreOrder(Stream t) { 

    Node n = new Node(t.GetNext()); 

    switch (n.Type) { 

     case Leaf: return; 

     case InternalNode: 

      PrintInorderFromPreOrder(t); 

      print(n.Value); 

      PrintInorderFromPreOrder(t); 

     default: 
      throw BadPreOrderException; 
    } 
} 

또한, 나는이 그 인공 아니라고 언급하고 싶습니다. 이 유형의 표현은 실제로 우리가 이진 트리를 직렬화해야 할 때 공간을 절약하기 위해 사용될 수 있습니다 : Efficient Array Storage for Binary Tree.