Leetcode #106. Կառուցեք երկուական ծառ Inorder-ից և Postorder Traversal-ից

Leetcode Daily Challenge [16 մարտի 2023]

Հաշվի առնելով երկու ամբողջ թվային զանգվածներ inorder և postorder, որտեղ inorder-ը երկուական ծառի անկանոն անցումն է, իսկ postorder-ը նույն ծառի հետպատվերի անցումն է, կառուցեք և վերադարձրեք երկուական ծառը:

Օրինակ 1.

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Սահմանափակումներ՝

• inorder-ը և postorder-ը բաղկացած են եզակի արժեքներից:
• postorder-ի յուրաքանչյուր արժեք նույնպես հայտնվում է inorder-ում:

Նախ, եկեք քննարկենք երկուական ծառի անցման մասին

1. Նախնական պատվեր անցում [NLR]

Նախ, այցելեք հանգույցը, ապա ձախ կողմը, իսկ հետո աջ կողմը: Դա DFS-ի վրա հիմնված անցում է:

2. Պատվերով անցում [LNR]

Նախ այցելեք ձախ կողմը, այնուհետև հանգույցը, այնուհետև աջ կողմը: Դա DFS-ի վրա հիմնված անցում է:

3. Պատվերից հետո անցում [LRN]

Նախ այցելեք ձախ կողմը, այնուհետև աջ կողմը, ապա աջ կողմը: Դա DFS-ի վրա հիմնված անցում է:

4. Level-order Traversal

Այս հանգույցում իմաստուն են անցման մակարդակը:

Բայց այս խնդրի դեպքում մենք պարզապես պետք է համաժամեցում գտնենք postorder [LRN] և inorder traversal [LNR] միջև:

Մենք գիտենք, որ հաջորդական անցման ժամանակ վերջին հանգույցը արմատային հանգույցն է, և մենք նաև գիտենք, որ հերթական անցման դեպքում արմատային հանգույցը գտնվում է ձախ ենթածառից հետո և աջ ենթածառից առաջ, որպեսզի մենք իմանանք, թե ինչն է ձախ կողմում և ինչ է գտնվում: աջ կողմը.

Քանի որ մենք ստուգում ենք հետպատվերի անցումը հակառակ հերթականությամբ, այնպես որ այն կդառնա NRL, ինչը նշանակում է, որ հաջորդ արմատային հանգույցը կլինի աջ կողմում, ոչ թե ձախ կողմում:

Հիմա եկեք դա այնքան հեշտ կոդավորենք, եթե ձեզ հարմար է ռեկուրսիոն

class Solution {
    
    int index;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index = postorder.length-1;
        return buildTree(inorder, postorder, 0, inorder.length-1);
    }

    public TreeNode buildTree(int[] inorder, int[] postorder, int start, int end) {
        if(start > end) return null;
    
        int nodeVal = postorder[index--];
        int inorderNodeIndex = findInorderNodeIndex(inorder, start, end, nodeVal);
    
        TreeNode root = new TreeNode(nodeVal);
        root.right = buildTree(inorder, postorder, inorderNodeIndex+1, end);
        root.left = buildTree(inorder, postorder, start, inorderNodeIndex-1);
        return root;
    }

    public int findInorderNodeIndex(int[] inorder, int start, int end, int nodeVal) {
        for(int i=start;i<=end;i++) {
            if(inorder[i] == nodeVal) return i;
        }
        return -1;
    }
}

Ժամանակի բարդություն.O(n²) { ամենավատ դեպքը, երբ ծառը ճիշտ թեքված երկուական ծառ է }

Տիեզերական բարդություն՝ O(1)

Ահա և տեսեք արդյունքները

Հիմա հետագան կարո՞ղ ենք այն օպտիմալացնել և որտեղ:

այո, քանի որ անորոշ անցման համար ինդեքս գտնելիս մենք օգտագործում ենք Գծային որոնում, ինչպես նաև չենք կարող այստեղ օգտագործել Երկուական որոնում, բայց քանի որ բոլոր արժեքները եզակի են, մենք կարող ենք ստեղծել քարտեզ արժեքների և ինդեքսների քարտեզագրման համար, որպեսզի կարողանանք ուղղակիորեն վերադարձնել ինդեքսը O(1)-ում: ժամանակ.

Ապա տեսնենք օպտիմիզացված կոդը

class Solution {
    
    int index;
    Map<Integer, Integer> inorderMap;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index = inorder.length-1;

        inorderMap = new HashMap<>();
        for(int i=0;i<=index;i++)
            inorderMap.put(inorder[i], i);

        return buildTree(inorder, postorder, 0, index);
    }

    public TreeNode buildTree(int[] inorder, int[] postorder, int start, int end) {
        if(start > end) return null;
    
        int nodeVal = postorder[index--];
        int inorderNodeIndex = inorderMap.get(nodeVal);
    
        TreeNode root = new TreeNode(nodeVal);
        root.right = buildTree(inorder, postorder, inorderNodeIndex+1, end);
        root.left = buildTree(inorder, postorder, start, inorderNodeIndex-1);
        return root;
    }
}

եկեք տեսնենք օպտիմիզացված կոդի արդյունքը

Այն այժմ օպտիմիզացված է:

Ժամանակի բարդություն՝O(n)

Տիեզերքի բարդություն՝ O(n) { քարտեզի օգտագործման համար }

Նմանատիպ հարց.

Կարծում եմ, հիմա դուք պետք է գոնե փորձեք այս խնդիրը, որը գրեթե նման է վերը նշված խնդրին: Եթե ​​դուք կարողանում եք լուծել այս մեկը, ապա կարող եք ենթադրել, որ հասկացել եք բլոգը:

Շնորհակալություն բոլորին !!!