LeetCode 검지 Offer 07.두 갈래 나무를 재건하다

6646 단어 Leet Code 제목.

제목


두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.링크

생각


맵은 노드의 아래 표지판을 기록하여 다음 순서가 루트 노드를 통해 노드의 위치를 정할 수 있도록 합니다.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int[] preorder;
    int[] inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        this.preorder = preorder;
        this.inorder = inorder;
        return buildTree(0, 0, inorder.length - 1);
    }

    TreeNode buildTree(int preIdx, int inLeft, int inRight){
        if(inLeft > inRight)return null;
        TreeNode root = new TreeNode(preorder[preIdx]);
        int inRootIdx = map.get(preorder[preIdx]);
        //preIdx 
        root.left = buildTree(preIdx + 1, inLeft, inRootIdx - 1);
        // , inRootIdx - inLeft 
        // preIdx+(1+inRootIdx-inLeft)
        root.right = buildTree(preIdx + 1 + inRootIdx - inLeft, inRootIdx + 1, inRight);
        return root;
    }
}

좋은 웹페이지 즐겨찾기