js를 이용한 이진 트리 재구성 알고리즘 분석

이 기사에서는 js를 사용하여 이진 트리를 재구성하는 알고리즘을 소개합니다. 이는 특정 참조 값이 있어 도움이 필요한 친구가 참조할 수 있습니다.

문제 설명

이진 트리의 선순 순회 및 순차 순회 결과를 입력하고 이진 트리를 재구성하십시오. 입력된 선순순회와 순순순회 결과에 반복되는 숫자가 포함되지 않는다고 가정한다. 예를 들어 선순 순회 시퀀스 {1,2,4,7,3,5,6,8}과 순차 순회 시퀀스 {4,7,2,1,5,3,8을 입력하면 ,6}, 이진 트리를 재구성하고 반환합니다.

Analytics

사전 순서 순회는 왼쪽, 가운데 순서이고 중간 순서 순회는 왼쪽, 중간, 오른쪽 순서이고 그 다음은 {1,2,4,7,3,5,6,8입니다. } 및 {4,7,2,1,5,3,8,6}, 1은 루트 노드이고 1은 순회 시퀀스를 두 부분으로 나누고 "4, 7, 2"는 노드입니다. 1의 왼쪽 하위 트리에 있는 "5, 3, 8, 6"은 1의 오른쪽 하위 트리에 있는 노드이며 재귀적으로 분해될 수 있습니다

코드 구현

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    var root = recon(0, pre.length-1, pre, 0, vin.length-1, vin);
    return root;
}

function recon(preStart, preEnd, pre, vinStart, vinEnd, vin){
    if(preStart > preEnd || vinStart > vinEnd) {
        return null;
    }

    var node = new TreeNode(pre[preStart]);

    for(var i = vinStart;i <p>관련 권장 사항: </p><p class="comments-box-content"><a href="http://www.php.cn/js-tutorial-406764.html" target="_blank" title="js中字符串的全排列的算法解析">전체 배열의 알고리즘 분석 of strings in js</a><br> </p><p class="mt20 ad-detail-mm hidden-xs"><a href="http://www.php.cn/js-tutorial-406767.html" target="_blank" title="js如何实现将上传图片并且压缩的方法">js에서 이미지 업로드 및 압축 방법을 구현하는 방법</a><br></p>

위 내용은 js를 이용한 이진 트리 재구성 알고리즘 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!