LeetCode 2020-11-09: Max Difference Between Node & Ancestor

しばらくメモを書くのをサボってしまったけど再開。

LeetCode daily challenge の問題 Maximum Difference Between Node and Ancestor (medium) の挑戦メモです。

問題の概要

• 先祖と子孫の関係にある二分木のノードの組について、そのノードたちが保持する値の差の絶対値を V とし、最大の V を求める

考え方

• やるべきことは明確なので、あとはそれをいかに効率よく解くかを考えるだけですね ☺️
• 深さ優先で木をたどることにしましょう
  • あるノードに到達したときに、ルートからそのノードに至るパスにおけるノードが保持する値の 最小値と最大値 を求めるようにしよう
    • 各ノードで最小値・最大値を求めるようにすれば、時間計算量はノードの数 n に対して O(n) となるね
  • この最小値・最大値の差を各ノードで計算し、最大の値をメソッドの戻り値として返せば OK かな
• 実装して submit → 一発 accept
  • Runtime 0ms で beats 100% 達成 💪

コード

class Solution {
    public int maxAncestorDiff(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return maxAncestorDiffRecursive(root, root.val, root.val);
    }

    int maxAncestorDiffRecursive(TreeNode node, int min, int max) {
        if (node == null) {
            return max - min;
        }

        min = Math.min(min, node.val);
        max = Math.max(max, node.val);
        return Math.max(maxAncestorDiffRecursive(node.left, min, max),
                maxAncestorDiffRecursive(node.right, min, max));
    }
}