categories: [컴퓨터 통식, 데이터 구조와 알고리즘, 검지 offer 시리즈]thumbnail: /images/fe/offer.jpg toc: true

검지offer 면접문제 37: 서열화 두 갈래 나무

두 함수를 실현하십시오. 각각 서열화와 반서열화 두 갈래 나무에 쓰십시오
두 갈래 나무의 서열화란 한 그루의 두 갈래 나무를 어떤 역행 방식의 결과에 따라 어떤 형식으로 문자열로 저장하여 메모리에 세워진 두 갈래 나무를 오래 보존할 수 있도록 하는 것을 말한다.서열화는 선순, 중순, 후순, 층순의 두 갈래 트리 역행 방식을 바탕으로 수정할 수 있습니다. 서열화의 결과는 문자열입니다. 서열화할 때 어떤 기호를 통해 빈 노드(#)를 나타냅니다!결점 값의 끝을 나타냅니다 (value!).
두 갈래 나무의 반서열화란 어떤 반복 순서에 따라 얻어진 서열화 문자열 결과str에 따라 두 갈래 나무를 재구성하는 것을 말한다.
서열화 과정에서 우리가 사용하는 것은 귀환의 전 서열을 훑어보는 것이다. 루트 노드부터 만나는 노드가 비어 있지 않으면 이 노드의 값을 그룹에 추가하고, 그렇지 않으면 그룹에 특수한 문자를 추가한다'#'
반서열화에 관해서 우리가 귀속으로 진행하는 서열화를 사용한 이상 귀속으로 반서열화를 할 수 있다.이외에도 귀속을 사용하지 않고 창고와 순환의 방식을 빌려 반서열화를 실현할 수 있다
먼저 귀속을 말하자면 이 문제의 귀속 사고방식은 전래된 한 줄에 대해서도 뿌리 노드, 왼쪽 나무, 오른쪽 나무로 나뉜다.그러면 먼저 첫 번째 문자를 하나의 루트 노드로 구축한 다음에 각각 좌우 트리를 귀속 구축할 수 있다(먼저 왼쪽 트리를 구축한 다음에 오른쪽 트리를 구축하고 이들의 순서가 관건임을 보장한다).귀속 종점은 전송된 열의 첫 번째 문자가 #번이면 현재 잎 노드에 구축되었음을 나타냅니다. 그러면 null로 돌아가서 다른 하위 트리를 계속 구축합니다.
코드는 다음과 같습니다 (반복 버전)

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
var arr = [];
function Serialize(pRoot)
{
    // write code here
    if(pRoot==null){
        arr.push('a');
    }else{
        arr.push(pRoot.val);
        Serialize(pRoot.left);
        Serialize(pRoot.right);
    }
        
}
function Deserialize(s)
{
    // write code here
    var node = null;
    if(arr.length<1){
        return null;
    }
    var number = arr.shift();
    if(typeof number == 'number'){
        node = new TreeNode(number);
        node.left = Deserialize(arr);
        node.right = Deserialize(arr);
    }
    return node;
}

그 다음은 비귀속이다. 우리는 현재 처리해야 할 노드를 창고로 기록해야 한다. 그래서 우리는 모든 노드에 Left와 Right를 추가해서 현재 이 노드가 왼쪽 트리와 오른쪽 트리에 모두 값을 부여했는지 감별한다. (노드가 부여되었든null이 부여되었든) 둘 다 값을 부여했다면: 처리되었고, 그렇지 않으면 처리되지 않은 것으로 기록된다.그러면 현재의 순환에 대해 먼저 창고 꼭대기 노드가 처리되었는지 판단하고 처리되면 창고를 팝업합니다. 그렇지 않으면 이 노드의 왼쪽 트리와 오른쪽 트리를 차례로 보고 처리되지 않은 트리에 노드를 추가합니다. 추가된 노드가null이 아니라면 이 새 노드를 계속 창고에 넣습니다.
코드는 다음과 같습니다 (비귀속 버전)

function TreeNode(x){
    this.val = x
    this.left = null
    this.right = null
    this.Left = 0
    this.Right = 0
}
let po = []
function Serialize(pRoot)
{
    // write code here
    if(pRoot === null){
        po.push('#')
        return null
    }
    else{
        po.push(pRoot.val)
        Serialize(pRoot.left)
        Serialize(pRoot.right)
    }
}

function Deserialize(s)
{
    // write code here
    let stack = []
    let root = (po[0] === '#') ? null : new TreeNode(po[0])
    if(root !== null){
        stack.push(root)
    }
    po.shift()
    while(po.length > 0 && stack.length > 0){
        if(stack[stack.length - 1].Left === 0){
            let k = (po[0] === '#') ? null : new TreeNode(po[0])
            stack[stack.length - 1].left = k
            stack[stack.length - 1].Left = 1
            if(k !== null){
                stack.push(k)
            }
            po.shift()

        }
        else if(stack[stack.length - 1].Right === 0){
            let k = (po[0] === '#') ? null : new TreeNode(po[0])
            stack[stack.length - 1].right = k
            stack[stack.length - 1].Right = 1
            if(k !== null){
                stack.push(k)
            }
            po.shift()
        }
        else if(stack[stack.length - 1].Left !== 0 && stack[stack.length - 1].Light !== 0){
            stack.pop()
        }
    }
    return root
}