LeetCode 2020-11-15: Range Sum of BST

LeetCode daily challenge の問題 Range Sum of BST (easy) の挑戦メモです。

(昨日 2020-11-14 の問題は時間内に解けなかったので残念ながらスキップ 😿)

問題の概要

• 与えられた二分探索木の値のうち、low 以上 high 未満の値を合計した結果を求める

考え方

• これは二分探索木を探索する練習問題みたいなやつですね
• low を下回る左の子ノードや high を上回る右の子ノードを切り捨てつつ深さ優先で再帰すればいいだけかな？
• 実装 → submit → accept
  • Runtime 0ms 達成 💪

コード

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }

        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }
        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }

        return root.val
                + rangeSumBST(root.left, low, high)
                + rangeSumBST(root.right, low, high);
    }
}