# LeetCode | Data Structure I | 14 Days Challenge | Day 13-14
###### tags: `LeetCode` `Data Structure I` `14 Days Challenge`
## Day 13

### [700. Search in a Binary Search Tree](https://leetcode.com/problems/valid-parentheses/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*You are given the root of a binary search tree (BST) and an integer val.*

>*Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.*

### 測資

Example 1:


:::info
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
:::

Example 2:


:::info
Input: root = [4,2,7,1,3], val = 5
Output: []
:::

### 數值範圍

The number of nodes in the tree is in the range [1, 5000].
1 <= Node.val <= 10^7^
root is a binary search tree.
1 <= val <= 10^7^

### 核心概念

==BST==

### 想法

BST(Binary Search Tree)遵循著**左節點必小於根，右節點必大於根，且數值必不重複**的規則。

因此若想縮減搜尋時間，則判斷該節點的值和Target的大小關係，判斷要走左還是右。

***time : 5 mins
time complexity : $O(n)$
space complexity : $O(1)$***

### 程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == nullptr) return nullptr;
        if(root->val == val) return root;
        if(val > root->val) return searchBST(root->right, val);
        else return searchBST(root->left, val);
    }
};

### [701. Insert into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.*

>*Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.*

### 測資

Example 1:


:::info
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:


:::

Example 2:

:::info
Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
:::

Example 3:

:::info
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]
:::

### 數值範圍

The number of nodes in the tree will be in the range [0, 10^4^].
-10^8^ <= Node.val <= 10^8^
All the values Node.val are unique.
-10^8^ <= val <= 10^8^
It's guaranteed that val does not exist in the original BST.

### 核心概念

==BSTe==

### 想法

單純的插入節點題目，謹記BST規則，當走到無路可走時(nullptr)，便新增一節點記憶體空間並插入。

***time : 10~15 mins
time complexity : $O(n)$
space complexity : $O(1)$***

### 程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void CreateNode(TreeNode* &root, int val){
        root = new TreeNode;
        root->val = val;
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == nullptr) CreateNode(root, val);
        else if(root->left == nullptr && val < root->val) CreateNode(root->left, val); 
        else if(root->right == nullptr && val > root->val) CreateNode(root->right, val);
        else if(val > root->val) insertIntoBST(root->right, val);
        else insertIntoBST(root->left, val);
        return root;
    }
};

## Day 14

### [98. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*Given the root of a binary tree, determine if it is a valid binary search tree (BST).*

>*valid BST is defined as follows:*

>* The left subtree of a node contains only nodes with keys less than the node's key.*
>
>* The right subtree of a node contains only nodes with keys greater than the node's key.*
>
>* Both the left and right subtrees must also be binary search trees.*

### 測資

Example 1:


:::info
Input: root = [2,1,3]
Output: true

:::

Example 2:


:::info
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
:::

### 核心概念

==BST==

### 數值範圍

The number of nodes in the tree is in the range [1, 10^4^].
-2^31^ <= Node.val <= 2^31^ - 1

### 想法

本題參考留言區大佬做法！
寫得真的很好看XD，想法都太美妙了。

利用根節點和孩子的大小關係進行判斷，**往左走，子節點必小於父節點，往右走，子節點必大於父節點**，因此若條件不符合此規則，則這不是一棵合法的BST!

***time : 45 mins
time complexity : $O(n)$
space complexity : $O(1)$***

### 程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool CheckBST(TreeNode* root, TreeNode* minn, TreeNode* maxx){
        if(root == nullptr) return true;
        if(minn != nullptr && minn->val >= root->val || maxx != nullptr && maxx->val <= root->val)
        return false;

        return CheckBST(root->left, minn, root) && CheckBST(root->right, root, maxx);
    }
    bool isValidBST(TreeNode* root) {
        if(root->left == nullptr && root->right == nullptr) return true;
        return CheckBST(root, nullptr, nullptr);
    }
};

### [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/two-sum-iv-input-is-a-bst/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.*

### 測資

Example 1:


:::info
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

:::

Example 2:


:::info
Input: root = [5,3,6,2,4,null,7], k = 28
Output: false
:::

### 核心概念

==BST==

### 數值範圍

The number of nodes in the tree is in the range [1, 104].
-10^4^ <= Node.val <= 10^4^
root is guaranteed to be a valid binary search tree.
-10^5^ <= k <= 10^5^

### 想法

我是利用set來實現，當s存在[k - val]這個key值，代表**val + (k-val) = k**，且兩數皆存在，則判斷為true，算是一個不錯的想法)?。

***time : 11 mins
time complexity : $O(n)$
space complexity : $O(n)$***

### 程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_set<int> s;
    bool findTarget(TreeNode* root, int k) {
        if(root == nullptr) return false;
        if( s.count(k - root->val) ) return true;
        else s.insert(root->val);
        return findTarget(root->left, k) || findTarget(root->right, k); 
    }
};

### [235. Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.*

>*According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”*

### 測資

Example 1:


:::info
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
:::

Example 2:


:::info
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
:::

Example 3:

:::info
Input: root = [2,1], p = 2, q = 1
Output: 2
:::

### 核心概念

==BST==

### 數值範圍

The number of the nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

### 想法

本題需要找到兩節點(p、q)的**共同最小父節點**，根據BST規則，可以歸納成以下條件:

假設p < q:
* 若p < root且p > root，則root為最小父節點
* 若p = root或q = root，則root為最小父節點
* 若p、q < root，則往左子節點尋找
* 若p、q > root，則往右子節點尋找

做題時須觀察條件，觀察、察覺、找出規則，**方能題題AC！**

最後恭喜自己完成了這14 Days Challenge，經過這14天的磨練(摧殘)，感覺自己的能力又更上一層樓，期待下次的挑戰，接下來應該會將本次挑戰中出現的資料結構、演算法出一篇篇的貼文做個整理，再開始下次的挑戰~ 謝謝大家~

***time : 12 mins
time complexity : $O(n)$
space complexity : $O(1)$***

### 程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->val > q->val) swap(p, q);
        if(p->val < root->val && q->val > root->val) return root;
        if(p->val == root->val || q->val == root->val) return root;
        if(p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
        if(p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};