1008. 구조 2차원 트리(leetcode)

2116 단어
주어진 선순위preorder와 일치하는 두 갈래 검색 트리 (binary search tree) 의 루트 결점을 되돌려줍니다.(돌이켜보면 두 갈래 검색 트리는 두 갈래 트리의 일종으로 그 모든 노드는 다음과 같은 규칙을 만족시킨다. node.left의 모든 후손, 값 총 node.val. 또한 먼저 노드의 값을 표시하고, 그 다음에 node.left, 그 다음에 node.right를 반복한다.)예: 입력: [8,5,1,7,10,12] 출력: [8,5,10,1,7,null,12] 알림: 1 <=preorder.length <= 100 순서preorder의 값은 다르다.
사고방식 2차원 검색 트리의 중차순 반복은 하강하지 않는 서열로 수조를 정렬하여 문제를 선차순 반복과 중차순 반복에 따라 2차원 트리를 구성하는 것으로 전환시킨다
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        
        int[] temp = Arrays.copyOf(preorder, preorder.length);
        Arrays.sort(temp);
        int[] inorder = temp;
        TreeNode root = buildMyTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
        return root;
    }
    
    public TreeNode buildMyTree(int[] preorder,
                                int preStart,
                                int preEnd,
                                int[] inorder,
                                int inStart,
                                int inEnd) {
        if (inStart > inEnd) {
            return null;
        }
        int value = preorder[preStart];
        int position = findPosition(inorder, inStart, inEnd, value);
    
        
        TreeNode root = new TreeNode(value);
        root.left = buildMyTree(preorder, preStart+1, preStart+position-inStart, inorder, inStart, position-1);
        root.right = buildMyTree(preorder, preStart+position-inStart+1, preEnd, inorder, position+1, inEnd);
        
        return root;
    }
    
    public int findPosition(int[] array, int start, int end, int key) {
        for (int i = start; i <= end; i++) {
            if (array[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
NestJS에 대한 기본 사항
【LeetCode】543. 두 갈래 나무의 지름

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage