Tugun va ajdod o'rtasidagi maksimal farq

Muammo haqida bayonot:

Ikkilik daraxtning ildizini hisobga olib, A va B turli tugunlari mavjud bo'lgan V ning maksimal qiymatini toping, bu erda V = | A.val - B.val | va A B ning ajdodidir.

(A tugun B ning ajdodidir, agar har ikkala A bolasi B ga teng bo'lsa yoki A ning har bir bolasi B ning ajdodidir).

1-misol:

Kirish: [8,3,10,1,6, null, 14, null, null, 4,7,13]
Chiqish natijasi: 7
Izoh:
Bizda turli xil ajdodlar farqlari mavjud, ularning ba'zilari quyida keltirilgan:
| 8 - 3 | = 5
| 3 - 7 | = 4
| 8 - 1 | = 7
| 10 - 13 | = 3
Barcha mumkin bo'lgan farqlar orasida 7 ning maksimal qiymati | 8 - 1 | tomonidan olinadi = 7.

Eslatma:

  1. Daraxtdagi tugunlar soni 2 dan 5000 gacha.
  2. Har bir tugun 0 dan 100000 gacha qiymatga ega bo'ladi.

Qaror:

Bu erda ko'rib chiqiladigan fokuslar:

  1. Ajdodlar haqida aytilganidek, chap va o'ng pastki satrlarni alohida ko'rib chiqish kerak.
  2. Mutlaq qiymat haqida o'ylashimiz kerak, min va max ikkalasi ham farqni oshirishi mumkin.

Algoritm:

Chapda yoki o'ngda min va maksimal qiymatni topishimiz kerak. Ildiz bilan taqqoslang va pastki qismlarda min / max qiymatini kuzatib boring. Ikkala pastki qismida ham DFS qilishimiz kerak. Ildizdan boshlash uchun min va max 0 bo'ladi.

dfs (root, root.val, root.val);

Bu erda dfs:

ommaviy statik bekor dfs (TreeNode ildizi, int min, int max) {
    if (root == null) return;
    / **
     * Ildiz bilan farqni hisoblash
     * * /
    int diff1 = Math.abs (root.val - min);
    int diff2 = Math.abs (root.val - max);
    / **
     * bu qiymatdan maksimal farqni toping
     * * /
    maxdiff = Math.max (maxdiff, diff1);
    maxdiff = Math.max (maxdiff, diff2);
    / **
     * ikkala daraxtda ham dfs
     * * /
    dfs (root.left, Math.min (min, root.val), Math.max (max, root.val));
    dfs (root.right, Math.min (min, root.val), Math.max (max, root.val));
}

Qaror:

ommaviy sinf MaxdifferenceNodeAndAncestor {
    statik int maxdiff;

    ommaviy statik void main (String [] args) {
        TreeNode ildizi = yangi TreeNode (8);
        root.left = yangi TreeNode (3);
        root.left.left = yangi TreeNode (1);
        root.left.right = yangi TreeNode (6);
        root.left.right.left = yangi TreeNode (4);
        root.left.right.right = yangi TreeNode (7);

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

    public static int maxAncestorDiff (TreeNode ildiz) {
        if (null == root) 0 ni qaytaring;
        maxdiff = 0;
        dfs (root, root.val, root.val);
        qaytish maxdiff;
    }

    ommaviy statik bekor dfs (TreeNode ildizi, int min, int max) {
        if (root == null) return;
        / **
         * Ildiz bilan farqni hisoblash
         * * /
        int diff1 = Math.abs (root.val - min);
        int diff2 = Math.abs (root.val - max);
        / **
         * bu qiymatdan maksimal farqni toping
         * * /
        maxdiff = Math.max (maxdiff, diff1);
        maxdiff = Math.max (maxdiff, diff2);
        / **
         * ikkala daraxtda ham dfs
         * * /
        dfs (root.left, Math.min (min, root.val), Math.max (max, root.val));
        dfs (root.right, Math.min (min, root.val), Math.max (max, root.val));
    }
}

Kodni bu erda topish mumkin.

LinkedIN-da meni kuzatib boring

Agar mening maqolam sizga yoqsa yoki sizga yoqsa, iltimos, mening notijorat tashkilotimga xayr-ehson qiling (Asmafaroque Foundation):