코딩테스트 준비 - Range Sum of BST

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : LeetCode

• 문제 : 938. Range Sum of BST

• 사용언어 : C#

• 난이도 : 하

• 풀이시간 : 18m 28s

• 유형 : 완전탐색, 이진트리, 트리

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

Constraints:

• The number of nodes in the tree is in the range [1, 2 * 104].

• 1 <= Node.val <= 105

• 1 <= low <= high <= 105

• All Node.val are unique.

문제 풀이 접근

이 문제는, 이진트리로 구성된 노드를 순회하는 문제다.
문제를 보고 이진트리 형태의 왼쪽, 오른쪽을 순회한다는 점에서 피보나치를 떠올렸다.
사실 왼쪽 오른쪽해서 맞으면 더하고 하는 것뿐이라, 비슷한 알고리즘이다.

다만 Return 값으로 받아서 연산하는 방식으로 하고싶었는데, 노드의 value로 판단해서 반환값과 완전탐색에 대한 제약을 설정하려니 방법이 애매해서 정적변수 하나두고 연산을 수행했다.

이 문제의 플로우는,
1. RootNode 기준으로 왼쪽, 오른쪽 돌린다.
2.값이 low, high를 포함한 사이의 값이 걸린다면 Ret 변수에 덧셈
3. 맨 처음 호출자로 돌아온 후 Ret 값 반환.

정답 작성 코드 (C#)

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;

///*
// * URL : https://leetcode.com/problems/range-sum-of-bst/description/
// */

namespace CodingTestProj
{
    internal class Program
    {

        static void Main(string[] args)
        {
            TreeNode root6 = new TreeNode(18, null, null);
            TreeNode root5 = new TreeNode(7, null, null);
            TreeNode root4 = new TreeNode(3, null, null);
            TreeNode root3 = new TreeNode(15, null, root6);
            TreeNode root2 = new TreeNode(5, root4, root5);
            TreeNode root1 = new TreeNode(10, root2, root3);

            int low = 7;
            int high = 15;
            Solution solu = new Solution();
            solu.RangeSumBST(root1,low,high);
        }
    }

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public class Solution
    {
        public static int Ret;
        public int RangeSumBST(TreeNode root, int low, int high)
        {
            // low , high 의 모든 노드 값의 합
            Ret = 0;
            RootRecursion(root, low, high);
            return Ret;
        }

        public void RootRecursion(TreeNode curRoot, int low, int high)
        {
            if (curRoot == null) return;

            if(curRoot.val >= low && curRoot.val <= high)
                Ret += curRoot.val;

            RootRecursion(curRoot.left, low, high);
            RootRecursion(curRoot.right, low, high);
        }
    }
}

코드 결과