Preorder 및 Children 문자에서 이진 트리를 형성하는 방법

Question

Preorder 목록에서 이진 트리를 만들고 각 노드에있는 자식 수의 시퀀스를 만드는 것이 문제입니다. 예 : "BAC"및 "200"은 "ABC"의 inorder 목록을 초래하는 하나의 입력이 될 수 있습니다.

현재 두 번째 문자열 (숫자가있는 문자)을 '2'로 확인하고, 두 개의 자식 '0', 자식이없고 'L', 왼쪽 자식이 있고 'R', 맞아. 기본적으로 트리의 각 지점이 끊기는 위치를 확인하기 위해 childCodes 순서를 처리

public static BinaryTree preOrderBuild(CharSequence charElements, 
     CharSequence childCodes) { 
    // TODO Auto-generated method stub. 
    BinaryTree build = new BinaryTree(); 
    char first; 
    if (childCodes.length() == 0) { 
     return new BinaryTree(); 
    } else { 
     first = childCodes.charAt(0); 
    } 
    if (first == '2') { 
     int sum = 1; 
     for (int i = 1; i < childCodes.length(); i++) { 
      if (childCodes.charAt(i) == 'R' || childCodes.charAt(i) == 'L') 
       sum += 0; 
      else if (childCodes.charAt(i) == '2') 
       sum += 1; 
      else if (childCodes.charAt(i) == '0') 
       sum--; 
      if (sum == 0) { 
       BinaryTree Left = preOrderBuild(
         charElements.subSequence(1, i + 1), 
         childCodes.subSequence(1, i + 1)); 
       BinaryTree Right = preOrderBuild(
         charElements.subSequence(i + 1, 
           charElements.length()), 
         childCodes.subSequence(i + 1, childCodes.length())); 
       build.merge(charElements.charAt(0), Left, Right); 
      } 
     } 
    } else if (first == 'R' || first == 'r') { 
     BinaryTree right = preOrderBuild(
       charElements.subSequence(1, charElements.length()), 
       childCodes.subSequence(1, childCodes.length())); 
     build.merge(charElements.charAt(0), new BinaryTree(), right); 
    } else if (first == 'L' || first == 'l') { 
     BinaryTree left = preOrderBuild(
       charElements.subSequence(1, charElements.length()), 
       childCodes.subSequence(1, childCodes.length())); 
     build.merge(charElements.charAt(0), left, new BinaryTree()); 
    } else { 
     build.merge(charElements.charAt(0), new BinaryTree(), 
       new BinaryTree()); 
    } 
    return build; 
} 

이렇게하려면 나는이 방법을 사용합니다. 문제는 큰 나무의 경우 처음 몇 개 항목 만 처리 한 다음 붕괴한다는 것입니다. (큰 트리의 예는 "ABCDEFGHIJKLMNOPQRSTU"이고 하위 코드가 "220022002200LRR20RLL0")

Answer 1

오른쪽에서 왼쪽으로 가면 재귀를 수행 할 필요가 없습니다.

A 
+-B 
| +-C 
| '-D 
'-E 
    +-F 
    | +-G 
    | '-H 
    '-I 
    +-J 
    | +-K 
    | '-L 
    '-M 
     +-N 
     | +-(null) 
     | '-O 
     | +-(null) 
     | '-P 
     |  +-Q 
     |  '-R 
     |  +-(null) 
     |  '-S 
     |   +-T 
     |   | +-U 
     |   | '-(null) 
     |   '-(null) 
     '-(null) 

:

데이터와

Stack<BinaryTree> stack = new Stack<BinaryTree>(); 

for (int i = childCodes.length() - 1; i >= 0; i--) { 
    char code = childCodes.charAt(i); 
    char name = charElements.charAt(i); 
    if (code == '0') { 
     stack.push(new BinaryTree(name, null, null)); 
    } 
    else if (code == 'L') { 
     stack.push(new BinaryTree(name, stack.pop(), null)); 
    } 
    else if (code == 'R') { 
     stack.push(new BinaryTree(name, null, stack.pop())); 
    } 
    else if (code == '2') { 
     stack.push(new BinaryTree(name, stack.pop(), stack.pop())); 
    } 
} 

return stack.pop(); 

, 그것은 다음과 같은 트리를 생성