Maksimaalne erinevus sõlme ja esivanema vahel

Probleemipüstituses:

Binaarse puu juurt arvestades leidke maksimaalne väärtus V, mille jaoks on olemas erinevad sõlmed A ja B, kus V = | A.val - B.val | ja A on B esivanem.

(Sõlm A on B esivanem, kui kumbki: mõni A laps on võrdne B-ga või mõni A-laps on B-i esivanem.)

Näide 1:

Sisend: [8,3,10,1,6, null, 14, null, null, 4,7,13]
Väljund: 7
Selgitus:
Esivanemate sõlmede erinevused on erinevad, mõned neist on toodud allpool:
| 8 - 3 | = 5
| 3 - 7 | = 4
| 8 - 1 | = 7
| 10 - 13 | = 3
Kõigist võimalikest erinevustest saadakse maksimaalne väärtus 7 väärtusega | 8 - 1 | = 7.

Märge:

  1. Puus olevate sõlmede arv on vahemikus 2 kuni 5000.
  2. Iga sõlme väärtus on vahemikus 0 kuni 100000.

Lahendus:

Nipid, mida siin kaaluda, on järgmised:

  1. Nagu esivanemate kohta öeldakse, tähendab see, et vasakpoolset ja paremat alamrühma tuleb vaadelda eraldi.
  2. Nagu peame arvestama absoluutväärtuse osas, võivad min ja max mõlemad muuta erinevuse.

Algoritm:

Peame leidma vasak- või parempoolse min ja max väärtuse. Võrrelge juurtega ja jälgige, kas mini- ja maksimumväärtus on alampreenides. Me peame DFS-i kasutama mõlemas alamtrees. Juurega alustades on min ja max 0.

dfs (juur, juur.val, juur.val);

Siin on dfs:

public static void dfs (TreeNode juur, int min, int max) {
    if (root == null) return;
    / **
     * Arvuta erinevus juuriga
     * * /
    int diff1 = Math.abs (root.val - min);
    int diff2 = Math.abs (root.val - max);
    / **
     * leida maksimaalne erinevus nendest väärtustest
     * * /
    maxdiff = Math.max (maxdiff, diff1);
    maxdiff = Math.max (maxdiff, diff2);
    / **
     * tehke mõlemas puus dfs
     * * /
    dfs (root.vasak, Math.min (min, root.val), Math.max (max, root.val));
    dfs (root.õigus, Math.min (min, root.val), Math.max (max, root.val));
}

Lahendus:

avaliku klassi MaxdifferenceNodeAndAncestor {
    staatiline int maxdiff;

    avalik staatiline tühine pea (string [] args) {
        TreeNode root = uus TreeNode (8);
        root.left = uus TreeNode (3);
        root.left.left = uus TreeNode (1);
        root.left.right = uus TreeNode (6);
        root.left.right.left = uus TreeNode (4);
        root.left.right.right = uus TreeNode (7);

        root.right = uus TreeNode (10);
        root.right.right = uus TreeNode (14);
        root.right.right.left = uus TreeNode (13);
        maxAncestorDiff (juur);
        System.out.println (maxdiff);
    }

    avalik staatiline int maxAncestorDiff (TreeNode'i juur) {
        if (null == root) tagastab 0;
        maxdiff = 0;
        dfs (juur, juur.val, juur.val);
        tagastamise maxdiff;
    }

    public static void dfs (TreeNode juur, int min, int max) {
        if (root == null) return;
        / **
         * Arvuta erinevus juuriga
         * * /
        int diff1 = Math.abs (root.val - min);
        int diff2 = Math.abs (root.val - max);
        / **
         * leida maksimaalne erinevus nendest väärtustest
         * * /
        maxdiff = Math.max (maxdiff, diff1);
        maxdiff = Math.max (maxdiff, diff2);
        / **
         * tehke mõlemas puus dfs
         * * /
        dfs (root.vasak, Math.min (min, root.val), Math.max (max, root.val));
        dfs (root.õigus, Math.min (min, root.val), Math.max (max, root.val));
    }
}

Koodi leiate siit.

Jälgi mind LinkedINis

Kui teile meeldib või meeldib mulle artikkel, annetage minu mittetulundusühingule (Asmafaroque sihtasutus):