leetcode

經過 Day 19, Day 20 的文章
今天從 leetcode 直接抓幾個練習
不過小弟才疏學淺，只能算是勉強通過而已XD

No 700. Search in a Binary Search Tree

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2
You should return this subtree:

      2     
     / \   
    1   3

這題的大意就是要從 BST(Binary Search Tree) 中找出 subtree
面對 BST，我的解法都是利用遞迴
先決定出中止條件：

 if (root != nullptr) {
     ...
 }
 return nullptr;

以上中止條件表示如果沒有節點了，就 return

寫遞迴式

if (root->val == val) return root;
else if (root->val > val) return searchBST(root->left, val);
else return searchBST(root->right->val);

以上遞迴表示如果當前的 val 就是我們要找的，那就可以回傳啦～
否則看是比較大還是比較小（BST 的特性）去遞迴右子樹或左子樹

合併起來：

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root != nullptr) {
            if (root->val == val) return root;
            else if (root->val > val) return searchBST(root->left, val);
            else return searchBST(root->right, val);
        }
        return nullptr;
    }
};

No 701. Insert into a Binary Search Tree

Given the tree:
        4
       / \
      2   7
     / \
    1   3
And the value to insert: 5
You can return this binary search tree:

         4
       /   \
      2     7
     / \   /
    1   3 5

題意為插入節點，簡單好懂

一樣先定義中止條件

   if (root == nullptr) {
        TreeNode* root = new TreeNode(val);
        return root;
 }

寫遞迴：

if (val < root->val) {
    root->left = insertIntoBST(root->left, val);
}
else {
    root->right = insertIntoBST(root->right, val);
}
return root;

以上同樣再次的利用 BST 特性，只要小於就左子樹，大於就右子樹

No 938. Range Sum of BST

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

這題比較有變化一點，不過同樣利用 BST 的特性
題意為給一個 BST，計算 range(L, R) 的總和

一樣先中止條件

if (root == nullptr) 
    return 0; 

判斷目前數值的範圍

if (root->val >= L && root->val <= R)
           sum += root->val;

左右子樹遞迴

rangeSumBST(root->left, L, R); 
rangeSumBST(root->right, L, R); 

以上就是今天的 leetcode 小練習。
題外話，第一次參加鐵人賽，同時也有兩個 conf 的志工，真ㄉ累
還要準備研究所推甄，真ㄉ更累
還不知道能推到哪，真ㄉ心很累