題目：

連結：https://leetcode.com/problems/two-sum-bsts/description/

• 等級：Medium

解題思路

class Solution {
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
            return dfs(root1, root2, target);
        }

        private boolean dfs(TreeNode root1, TreeNode root2, int target){
            if(root1 == null){
                return false;
            }

            TreeNode node = root2;
            while(node != null){
                if(node.val > target - root1.val){
                    node = node.left;
                }else if(node.val < target - root1.val){
                    node = node.right;
                }else{
                    return true;
                }
            }

            return dfs(root1.left, root2, target) || dfs(root1.right, root2, target);
        }
}

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

題目：

連結：

• 等級：Easy

解題思路

1. 使用index紀錄陣列位置
2. 迴圈判斷取得的值大於index位置的值，就將數值放在index位置後．

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

題目：153. Find Minimum in Rotated Sorted Array

連結：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/

• 等級：Medium

解題思路

1. Binnary serach
2. nums[mid] > nums[start] 且 nums[mid] > nums[end] 移動start
3. 反之移動end

class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1)
            return nums[0];
        //binary search
        int start = 0,end = nums.length - 1;
        while (start < end)
        {
            int mid = start + (end - start) / 2;
            if (mid > 0 && nums[mid] < nums[mid-1])
                return nums[mid];
            if (nums[start] <= nums[mid] && nums[mid] > nums[end])
                start = mid + 1;
            else
                end = mid - 1; 

        }
        return nums[start];
    }
}

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