Հաշվեք հանգույցները ամբողջական երկուական ծառի մեջ

Ենթադրենք, մեզ տրվել է այս խնդիրը.

Հաշվի առնելով ամբողջական երկուական ծառի root-ը, վերադարձրեք ծառի հանգույցների թիվը:

Ըստ Վիքիպեդիայի-ի՝ յուրաքանչյուր մակարդակ, բացառությամբ, հնարավոր է, վերջինի, ամբողջությամբ լցված է ամբողջական երկուական ծառի մեջ, և վերջին մակարդակի բոլոր հանգույցները հնարավորինս հեռու են մնացել: Այն կարող է ունենալ 1-ից 2h հանգույցներ՝ ներառյալ վերջին h մակարդակը:

Նախագծեք ալգորիթմ, որն աշխատում է O(n)-ից պակաս ժամանակով:

Ամբողջական երկուական ծառ

Նախ, եկեք սահմանենք, թե ինչ է ամբողջականերկուական ծառը: Ամբողջական Երկուական ծառը ծառի կառուցվածք է, որն ունի nխորություն, և յուրաքանչյուր հանգույց մինչև n-1 խորությունը լցված է: nխորության վրա ծառի կառուցվածքը լցված է ձախից և լցված է դեպի աջ:

Վերևի նկարում կարող եք տեսնել, որ ներքևի մակարդակը, n խորության վրա մասամբ լցված է դեպի ձախ: Քանի դեռ հանգույցները լցված են ներքևում՝ ձախից -› աջից, մենք կարող ենք ասել, որ երկուական ծառը ամբողջական է:

Ինչպե՞ս ենք սա լուծում:

Խնդրում այն ​​մեզ հարցնում է, թե արդյոք մենք կարող ենք դա լուծել O(n)-ից քիչ ժամանակում: Եթե ​​մենք օգտագործենք որևէ մեթոդ, ինչպիսին է լայնության առաջին որոնումը կամ խորությունը առաջին որոնումը, վստահաբար, մենք կարող ենք դա հեշտությամբ լուծել, բայց դա կլինի O(n) ժամանակում:

Մեզ մնում է միայն անցնել յուրաքանչյուր հանգույցի վրայով և ավելացնել հաշվիչը, բայց դա այն չէ, ինչ հարցն է պահանջում: Մենք պետք է լուծենք սա ավելի արագ, քան O(n):

Սա ավելի օպտիմալ կերպով լուծելու համար մենք կարող ենք այս խնդիրը բաժանել երկու մասի.

• Գտեք հանգույցների քանակը մինչև վերջին մակարդակը (վերին մակարդակները):
• Գտնելով հանգույցների թիվը վերջին մակարդակում (ներքևի մակարդակ):

public int findDepth(TreeNode cur, int depth) {
    if(cur == null) return depth;
    depth++;
    return findDepth(cur.left, depth);
}

public int countNodes(TreeNode root) {

    int depth = findDepth(root, 0);

    if(depth == 0 || depth == 1) return depth;

    int numOfUpperNodes = (int) (Math.pow(2, depth-1)-1);

    ...
}

public int findDepth(TreeNode cur, int depth) {
    if(cur == null) return depth;
    depth++;
    return findDepth(cur.left, depth);
}

public int countNodes(TreeNode root) {

    int depth = findDepth(root, 0);

    if(depth == 0 || depth == 1) return depth;

    int numOfUpperNodes = (int) (Math.pow(2, depth-1)-1);

    int left = 0;
    int right = numOfUpperNodes; // On the level below there is numberOfUpperNodes + 1 (index is -1)

    // Perform binary search
    while(left < right) {
        int idxToFind = (int) Math.ceil((double)(left + right) / 2);
        boolean nodeExists = nodeExists(idxToFind, depth, root, numOfUpperNodes); // Check if node exists during at the index to find
        if(nodeExists) {
            left = idxToFind;
        } else {
            right = idxToFind-1;
        }
    }
    return numOfUpperNodes + left + 1;
}

Այժմ, մենք պետք է պարզենք, թե ինչպես ենքորոշում, արդյոք հանգույցը գոյություն ունի ներքևի մակարդակի որոշակի ինդեքսում:

Արդյո՞ք հանգույցը գոյություն ունի:

Այժմ մենք գիտենք, թե ինչպես օգտագործել երկուական որոնումը ներքևի մակարդակում՝ գտնելու վերջին ինդեքսը, որտեղ գոյություն ունի հանգույց: Բայց քանի որ տվյալները պահվում են ծառի կառուցվածքի ստորին մակարդակում, մենք պետք է որոշենք, թե ինչպես կարելի է հասնելյուրաքանչյուր ինդեքսին:

Եկեք նայենք կոդը, որը մենք օգտագործում ենք՝ որոշելու համար, թե արդյո՞ք հանգույցը գոյություն ունի ներքևի մակարդակի ինդեքսում:

public boolean nodeExists(
  int idxToFind, 
  int depth, 
  TreeNode node, 
  int numOfUpperNodes) {

    int left = 0;
    int right = numOfUpperNodes;
    int count = 1;

    while(count < depth) {
        int mid = (int) Math.ceil((double)(left + right) / 2);
        if(idxToFind >= mid) {
            node = node.right;
            left = mid;
        } else {
            node = node.left;
            right = mid - 1;
        }
        count++;
    }

    return node != null;
}

Վերևի կոդում մուտքերն են.

• idxToFind (ինդեքս գտնելու համար)
• depth
• node (արմատը)
• numOfUpperNodes (վերին հանգույցների քանակը)

Մենք սահմանել ենք left և right համապատասխանաբար 0 և numOfUpperNodes: Մենք կարող ենք պատկերացնել left-ը և right-ը որպես ստորին շերտի սահմաններ: Մեր դեպքում սա 0և 7 է:

Մենք գործարկում ենք հանգույց, մինչդեռ count ‹ depth և ավելացնում ենք count օղակի յուրաքանչյուր կրկնման ժամանակ: Սա այնպես է, որ մենք ավելի չգնանք ստորին մակարդակից:

Ներքևի մակարդակում, երբ մենք կանգ առնենք, մեզ կամ կմնա node, կամ node-ը ցույց կտա null:

Ներքևում գտնվող ճիշտ ինդեքսի մեր ճանապարհը գտնելու համար.

Յուրաքանչյուր կրկնության մեջ մենք սահմանում ենք mid կետ:

Եթե ​​idxToFind-ը մեծ է կամ հավասար է միջինին, մենք գնում ենք աջ:

• Մենք սահմանել ենք node = node.right
• Մենք տեղափոխում ենք left__________

Եթե ​​idxToFind-ը միջինից փոքր է, մենք գնում ենք ձախ:

• Մենք սահմանել ենք node = node.left
• Մենք տեղափոխում ենք right mid — 1

Նայեք այս անիմացիային.

Մտածեք դրա մասին այսպես.

Count սկսվում է 1-ին:

Սկզբում մենք կարող ենք արմատից շարժվել ցանկացած ուղղությամբ: Սահմաններն են0–7։ Եթե ​​mid-ը 4 է, ապա մենք պետք է գնանք ձախ, քանի որ մեր հանգույցը գտնվում է ինդեքս 3-ում և չի կարող գոյություն ունենալ mid.Count ավելացումներից հետո: դեպի 2.

Այն բանից հետո, երբ մենք ընտրում ենք գնալ ձախ, այժմ սահմաններն են0–3: Ահա թե ինչու մենք right-ը սահմանեցինք mid-1: mid-ը 2 է, իսկ մեր ցուցանիշը 3 է, ուստի մենք պետք է գնանք ճիշտ: Count-ն այժմ 3 է:

Երբ մենք գնում ենք աջ, սահմանները նորից փոքրանում են մինչև 2–3: Վերջապես, մեր mid-ը 3 է, ուստի մենք նորից գնում ենք աջ: Count այժմ 4 է:

Քանի որ count-ն այժմ հավասար է 4-ի, այն խախտում է while օղակը, և քանի որ node-ը, որի վրա մենք հայտնվեցինք, ոչ զրոյական էր, մենք կարող ենք վերադարձնել true:

Եթե, օրինակ, մեր ինդեքսը լիներ5, ապա կրկնությունները նման կլինեն.

• Ճիշտ
• Ձախ
• Ճիշտ

Վերջին կրկնության ժամանակ, երբ աջ տեղափոխվենք 6 հանգույցից, node-ը ցույց կտա null: Սա կդարձնի ֆունկցիան վերադառնալ false:

Կոդ

Հիմա, երբ մենք ամեն ինչ հավաքում ենք, մենք ունենք մեր լուծումը։

public int countNodes(TreeNode root) {

    int depth = findDepth(root, 0);

    if(depth == 0 || depth == 1) return depth;

    int numOfUpperNodes = (int) (Math.pow(2, depth-1)-1);

    int left = 0;
    int right = numOfUpperNodes; // On the level below there is numberOfUpperNodes + 1 (index is -1)

    // Perform binary search
    while(left < right) {
        int idxToFind = (int) Math.ceil((double)(left + right) / 2);
        boolean nodeExists = nodeExists(idxToFind, depth, root, numOfUpperNodes); // Check if node exists during at the index to find
        if(nodeExists) {
            left = idxToFind;
        } else {
            right = idxToFind-1;
        }
    }
    return numOfUpperNodes + left + 1;
}

public boolean nodeExists(
  int idxToFind, 
  int depth, 
  TreeNode node, 
  int numOfUpperNodes) {

    int left = 0;
    int right = numOfUpperNodes;
    int count = 1;

    while(count < depth) {
        int mid = (int) Math.ceil((double)(left + right) / 2);
        if(idxToFind >= mid) {
            node = node.right;
            left = mid;
        } else {
            node = node.left;
            right = mid - 1;
        }
        count++;
    }

    return node != null;
}

public int findDepth(TreeNode cur, int depth) {
    if(cur == null) return depth;
    depth++;
    return findDepth(cur.left, depth);
}

Կատարման վերլուծություն

Ժամանակի բարդություն.

• Ձեր countNodes ֆունկցիայի ժամանակային բարդության գերիշխող գործոնը երկուական որոնման օղակն է: Քանի որ դուք կատարում եք երկուական որոնում հավասարակշռված երկուական ծառի վրա, երկուական որոնման ժամանակային բարդությունը O(log n) է, որտեղ «n»-ը երկուական ծառի հանգույցների թիվն է:
• findDepth ֆունկցիան, որը հաշվարկում է ծառի խորությունը, ունի O(log n) ժամանակային բարդություն հավասարակշռված երկուական ծառում, քանի որ այն անցնում է ձախ ենթածառով: nodeExists ֆունկցիան նաև կատարում է երկուական որոնում յուրաքանչյուր մակարդակում, և քանի որ երկուական որոնման խորությունը լոգարիթմական է, դրա ժամանակային բարդությունը O(log n է):
• Ընդհանուր առմամբ, countNodes ֆունկցիայի ժամանակային բարդության մեջ գերակշռում է երկուական որոնումը, ուստի այն O(log n) է, որտեղ «n»-ը երկուական ծառի հանգույցների թիվն է:

Տիեզերական բարդություն.

• Ձեր countNodes ֆունկցիայի տարածության բարդությունը որոշվում է findDepth ֆունկցիայի և nodeExists ֆունկցիայի ռեկուրսիոն կույտերի համար պահանջվող տարածությամբ: Քանի որ այս ֆունկցիաները կոչվում են ռեկուրսիվորեն ծառի յուրաքանչյուր մակարդակի համար, ռեկուրսիայի առավելագույն խորությունը երկուական ծառի բարձրությունն է։
• Հավասարակշռված երկուական ծառում բարձրությունը log₂(n) է, որտեղ «n»-ը հանգույցների թիվն է: Այսպիսով, ռեկուրսիոն կույտերի համար պահանջվող առավելագույն տարածությունը O(log n) է:
• Բացի այդ, դուք օգտագործում եք մշտական ​​քանակությամբ լրացուցիչ տարածություն այնպիսի փոփոխականների համար, ինչպիսիք են depth, numOfUpperNodes, left, right, idxToFind և nodeExists բուլյան գործառույթը: Այս փոփոխականները կախված չեն մուտքագրման չափից և մշտական ​​տարածություն են:
• Հետևաբար, countNodes ֆունկցիայի ընդհանուր տարածության բարդությունը O(log n) է` պայմանավորված ռեկուրսիոն կույտի տարածությամբ և փոփոխականների կողմից օգտագործվող հաստատուն տարածությամբ:

Մենք գտել ենք լուծում, որն ավելի լավ է գործում, քանO(n): Հուսով եմ, որ սա օգտակար էր:

LeetCode արդյունք