1026. Maximum Difference Between Node and Ancestor

leetcode medium

#csharp#graph#leetcode#math#medium#recursion#tree#two-pointers

Task

Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.

Пример:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]

Output: 7

C# solution

matched/original

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    public int MaxAncestorDiff(TreeNode root) {
        return Dfs(root, root.val, root.val);
    }
    
    private int Dfs(TreeNode node, int minVal, int maxVal) {
        if (node == null) return maxVal - minVal;
        minVal = Math.Min(minVal, node.val);
        maxVal = Math.Max(maxVal, node.val);
        int left = Dfs(node.left, minVal, maxVal);
        int right = Dfs(node.right, minVal, maxVal);
        return Math.Max(left, right);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
class Solution {
public:
    public int MaxAncestorDiff(TreeNode root) {
        return Dfs(root, root.val, root.val);
    }
    
    private int Dfs(TreeNode node, int minVal, int maxVal) {
        if (node == null) return maxVal - minVal;
        minVal = min(minVal, node.val);
        maxVal = max(maxVal, node.val);
        int left = Dfs(node.left, minVal, maxVal);
        int right = Dfs(node.right, minVal, maxVal);
        return max(left, right);
    }
}

Java solution

matched/original

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int maxAncestorDiff(TreeNode root) {
        return dfs(root, root.val, root.val);
    }
    
    private int dfs(TreeNode node, int minVal, int maxVal) {
        if (node == null) return maxVal - minVal;
        minVal = Math.min(minVal, node.val);
        maxVal = Math.max(maxVal, node.val);
        int left = dfs(node.left, minVal, maxVal);
        int right = dfs(node.right, minVal, maxVal);
        return Math.max(left, right);
    }
}

JavaScript solution

matched/original

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    maxAncestorDiff(root) {
        const dfs = (node, minVal, maxVal) => {
            if (!node) return maxVal - minVal;
            minVal = Math.min(minVal, node.val);
            maxVal = Math.max(maxVal, node.val);
            const left = dfs(node.left, minVal, maxVal);
            const right = dfs(node.right, minVal, maxVal);
            return Math.max(left, right);
        };
        return dfs(root, root.val, root.val);
    }
}

Explanation

Algorithm

Рекурсивный обход дерева:

Используйте рекурсивную функцию для обхода дерева. Передавайте минимальное и максимальное значения, встреченные на пути от корня к текущему узлу.

Обновление максимальной разницы:

При посещении каждого узла обновляйте минимальное и максимальное значения. Вычисляйте разницу между текущим значением узла и минимальным и максимальным значениями на пути. Обновляйте максимальную разницу, если текущая разница больше.

Рекурсивный вызов для детей:

Рекурсивно вызывайте функцию для левого и правого поддерева, передавая обновленные минимальное и максимальное значения.

😎