Максимална разлика между възел и прародител

Декларация за проблем:

Като се има предвид коренът на двоично дърво, намерете максималната стойност V, за която съществуват различни възли A и B, където V = | A.val - B.val | и А е прародител на Б.

(Възел A е прародител на B, ако едно от двете: всяко дете на A е равно на B, или всяко дете на A е прародител на Б.)

Пример 1:

Вход: [8,3,10,1,6, null, 14, null, null, 4,7,13]
Изход: 7
Обяснение:
Имаме различни различия във възел на предците, някои от които са дадени по-долу:
| 8 - 3 | = 5
| 3 - 7 | = 4
| 8 - 1 | = 7
| 10 - 13 | = 3
Сред всички възможни разлики максималната стойност на 7 се получава от | 8 - 1 | = 7.

Забележка:

  1. Броят на възлите в дървото е между 2 и 5000.
  2. Всеки възел ще има стойност между 0 и 100000.

Решение:

Трикове за разглеждане тук са:

  1. Както се говори за прародител, това означава, че лявото и дясното поддърво трябва да се разглеждат отделно.
  2. Тъй като трябва да вземем предвид абсолютната стойност, min и max и двете могат да направят разлика по-висока.

алгоритъм:

Трябва да намерим минимална и максимална стойност вляво или вдясно. Сравнете с root и следете минималната / максималната стойност в подредовете. Ние трябва да DFS в двата подреда. За начало с корен, min и max ще бъдат 0.

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

Ето dfs:

публични статични void dfs (корен на TreeNode, int min, int max) {
    ако (root == null) се върне;
    / **
     * Изчислете разликата с корен
     * * /
    int diff1 = Math.abs (root.val - мин.);
    int diff2 = Math.abs (root.val - max);
    / **
     * намери максималната разлика от тези стойности
     * * /
    maxdiff = Math.max (maxdiff, diff1);
    maxdiff = Math.max (maxdiff, diff2);
    / **
     * направете 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));
}

Решение:

публичен клас MaxdifferenceNodeAndAncestor {
    статичен int maxdiff;

    public static void main (String [] args) {
        TreeNode root = нов TreeNode (8);
        root.left = нов TreeNode (3);
        root.left.left = нов TreeNode (1);
        root.left.right = нов TreeNode (6);
        root.left.right.left = нов TreeNode (4);
        root.left.right.right = нов TreeNode (7);

        root.right = нов TreeNode (10);
        root.right.right = нов TreeNode (14);
        root.right.right.left = нов TreeNode (13);
        maxAncestorDiff (основа);
        System.out.println (maxdiff);
    }

    публичен статичен int maxAncestorDiff (корен на TreeNode) {
        ако (null == root) върнете 0;
        maxdiff = 0;
        dfs (root, root.val, root.val);
        връщане maxdiff;
    }

    публични статични void dfs (корен на TreeNode, int min, int max) {
        ако (root == null) се върне;
        / **
         * Изчислете разликата с корен
         * * /
        int diff1 = Math.abs (root.val - мин.);
        int diff2 = Math.abs (root.val - max);
        / **
         * намери максималната разлика от тези стойности
         * * /
        maxdiff = Math.max (maxdiff, diff1);
        maxdiff = Math.max (maxdiff, diff2);
        / **
         * направете 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));
    }
}

Код можете да намерите тук.

Следвайте ме на LinkedIN

Ако харесвате или харесвате моята статия, моля, дарете за моята нестопанска цел (фондация Асмафарок):