[LeetCode]105. 이전 순서와 중간 순서 반복 서열 구조 두 갈래 나무 (귀속)

1724 단어

제목.


한 그루의 나무의 앞차례와 중차례에 따라 두 갈래 나무를 구성한다.
주의: 트리에 중복된 원소가 없다고 가정할 수 있습니다.

문제풀이

  • 귀속
  • 귀속전참: 이 서브트리에 대응하는 전 서열과 중 서열(시작 끝 지침으로 표시하면 됨)
  • 각 층 확정: new 현재 하위 나무 뿌리 노드, 좌우 아이는 각각 귀속된 귀환값
  • 을 부여한다.
  • 귀속 종료 조건: 현재 하위 나무 뿌리 노드
  • 로 귀환
  • HashMap을 사용하여 현재 하위 트리 루트 노드가 중순으로 옮겨다니는 위치를 기록하여 매번 찾기 쉽습니다.
  • 왼쪽 트리 노드 수량으로 idx
  • 찾기

    코드

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        private HashMap indexMap = new HashMap<>();
        private int[] preorder;
        private int[] inorder;
    
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            for (int i = 0; i < inorder.length; ++i) {
                indexMap.put(inorder[i], i);
            }
            this.preorder=preorder;
            this.inorder=inorder;
    
            return buildTreeHelper(0, preorder.length, 0, inorder.length);
        }
    
        private TreeNode buildTreeHelper(int preorderL, int preorderR, int inorderL,
                int inorderR) {
            if (preorderL == preorderR) {
                return null;
            }
            TreeNode root = new TreeNode(preorder[preorderL]);
            int rootIdx = indexMap.get(preorder[preorderL]);//  idx
            int leftTreeNodeCnt = rootIdx - inorderL;//  
            int inorderSplitIdx = preorderL + 1 + leftTreeNodeCnt;
    
            root.left = buildTreeHelper(preorderL + 1, inorderSplitIdx, inorderL, rootIdx);
            root.right = buildTreeHelper(inorderSplitIdx, preorderR, rootIdx + 1, inorderR);
            return root;
        }
    }

    좋은 웹페이지 즐겨찾기