題目：700. Search in a Binary Search Tree

連結：https://leetcode.com/problems/search-in-a-binary-search-tree/description/

• 等級：Easy

解題思路

1. 左樹小於右樹，左中右尋找．

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
		while (root != null)
		{
			if ( val < root.val ) root = root.left;
			else if ( val > root.val ) root = root.right;
			else return root;
		}
		return root;
    }
}

• Time complexity: O(n)
• Space complexity: O(1)

題目：701. Insert into a Binary Search Tree

連結：https://leetcode.com/problems/insert-into-a-binary-search-tree/description/

• 等級：Easy

lass Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        if (val > root.val)
            root.right = insertIntoBST(root.right,val);
        else if (val < root.val)
            root.left = insertIntoBST(root.left, val);
        return root;
    }
}

• Time complexity: O(n)
• Space complexity: O(n)

題目：450. Delete Node in a BST

連結：https://leetcode.com/problems/insert-into-a-binary-search-tree/description/

• 等級：Medium

class Solution {
    public TreeNode minValueNode(TreeNode root) {
        TreeNode curr = root;
        while(curr != null && curr.left != null) {
            curr = curr.left;
        }
        return curr;
    }
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;
        if (key > root.val)
            root.right = deleteNode(root.right, key);
        else if (key < root.val)
            root.left = deleteNode(root.left, key);
        else
            {
                if (root.left == null)
                    return root.right;
                else if (root.right == null)
                    return root.left;
                else
                {
                    //1.找右邊最小的點當root
                    //2.再刪除他
                     TreeNode minNode = minValueNode(root.right);
                        root.val = minNode.val;
                        root.right = deleteNode(root.right, minNode.val);
                }
            }
            return root;
    }
}

• Time complexity: O(n)
• Space complexity: O(n)