Posted Updated LeetCode / Medium / 复习2 minutes read (About 341 words)

99. Recover Binary Search Tree

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

DFS中序搜索，额外记录访问的前一个节点。
如果当前节点与前一个节点的顺序不对，则暂且认为先后两个节点的位置均不正确。
（前一个大于后一个的值，由于是第一个不满足递增条件的位置，因此前一个的位置一定是错误的。但此时当前值不一定是错误的。）
继续递归，如果发现新的节点位置不正确，则后一个节点位置正确，更新当前节点为不正确的节点。
（由于是第二个不满足递增条件的位置，因此当前值是错误的。）
交换两个位置不正确的节点的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode prev;
    boolean flag;
    TreeNode[] wrong;
    public void recoverTree(TreeNode root) {
        wrong = new TreeNode[2];
        prev = new TreeNode(Integer.MIN_VALUE);
        flag = true;
        
        dfs(root);
        
        int swap = wrong[0].val;
        wrong[0].val = wrong[1].val;
        wrong[1].val = swap;
        
        
    }
    
    private void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        if(prev.val > root.val){
            if(flag){
                wrong[0] = prev;
                flag = false;
            }
            wrong[1] = root;
        }
        prev = root;
        dfs(root.right);
    }
}
Posted Updated LeetCode / Mediuma minute read (About 164 words)

230. Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

DFS搜索，遍历的时候更新全局变量count。
采用中序搜索，当count等于k时，将全局变量ans设置为root.val。
搜索完毕返回ans。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ans;
    int count;
    public int kthSmallest(TreeNode root, int k) {
        ans = -1;
        count = 0;
        dfs(root,k);
        return ans;
    }
    
    private void dfs(TreeNode root, int k){
        if(root == null){
            return;
        }
        dfs(root.left,k);
        count++;
        if (k == count){
            ans = root.val;
        }
        dfs(root.right,k);
    }
}
240. Search a 2D Matrix II
Posted Updated LeetCode / Medium / 复习a minute read (About 137 words)

240. Search a 2D Matrix II

Question

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Solution

将起始点设置为第一行的最后一列。
如果搜寻目标大于该点则向下搜索。
如果搜寻目标小于该点则向左搜索。

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        
        while(i < matrix.length && j >= 0){
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 134 words)

56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

先对数组进行排序。
遍历数组，当前一个子数组与后一个子数组有重叠时，合并数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[0],b[0]));

        int i = 0;
        List<int[]> ans = new ArrayList();
        while( i < intervals.length-1 ){
            if(intervals[i][1] >= intervals[i+1][0]){
                intervals[i+1][0] = intervals[i][0];
                intervals[i+1][1] = Math.max(intervals[i][1], intervals[i+1][1]);
                intervals[i] = null;
            }
            i++;
        }
        
        for(int[] interval : intervals){
            if(interval != null){
                ans.add(interval);
            }
        }
        return ans.toArray(new int[ans.size()][2]);
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 228 words)

82. Remove Duplicates from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

使用队列暂存遍历的节点。
初始化prev为一个dummy节点。
如果当前节点不等于队列里节点的值，则倾倒出队列里的值。如果队列此时只有一个值，则将其添加到prev.next。
遍历完毕后如果队列内只有一个值则将其设置到prev.next。
最后返回dummy.next。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Queue<ListNode> q = new LinkedList();
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        ListNode curr = head; 
        while(curr != null){
            if(q.isEmpty() || curr.val == q.peek().val){
                q.offer(curr);
                curr = curr.next;
            }
            else{
                if(q.size()==1){
                    prev.next = q.poll();
                    prev = prev.next;
                    prev.next = null;
                }
                else{
                    q.clear();   
                }
            }
        }
        
        if(q.size()==1){
            prev.next = q.poll();
        }
        
        return dummy.next;
    }

}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 394 words)

162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

二分搜索，由于只需要搜索任意一个山峰，因此只要向上走，一定可以走到一个峰。
当中值的下一个值是增长时（向上爬山），则更新左侧指针的位置为中值+1。继续搜索下一个中值。
否则更新右侧指针的位置为当前中值，等于向左侧进行搜索。
最后返回左侧指针停留的位置。
时间复杂度为O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findPeakElement(int[] num) {
        int left = 0;
        int right = num.length - 1;

        while (left < right) {
            int mid1 = (right - left) / 2 + left;
            int mid2 = mid1 + 1;
            if (num[mid1] < num[mid2])
                left = mid1+1;
            else
                right = mid1;
        }
        return left;
    }
}

一次遍历，找到峰值，返回其index。
时间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findPeakElement(int[] nums) {
        int peak = 0;
        
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > nums[peak]){
                peak = i;
            }
        }
        return peak;
    }
}

分治法，每次将数组分为两组，向下递归。
当数组长度为1时返回元素，比较返回来的两个数值的大小。
返回其中的峰值index。
此解法时间为O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findPeakElement(int[] nums) {
        return findPeak(nums,0,nums.length-1);
    }
    
    private int findPeak(int[] nums, int left, int right){
        if(left == right){
            return left; 
        }
        int mid = left + (right - left) / 2;
        int i = findPeak(nums, left, mid);
        int j = findPeak(nums, mid+1, right);
        
        if(nums[i] > nums[j]){
            return i;
        }
        else{
            return j;
        }
    }
}
48. Rotate Image
Posted Updated LeetCode / Medium / 复习3 minutes read (About 505 words)

48. Rotate Image

Question

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Solution 1

此方法是in-place算法。

visited[][]数组记录访问情况，遍历所有位置，如果已访问则跳过。
循环替换矩阵上的每一个位置，如果已经访问过则break。
如果未访问则将要替换位置的值保存，并且在visited[][]数组上记录。
然后继续遍历替换过的位置。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] visited = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(visited[i][j] == 1) continue;
                int x = i, y = j;
                int value = matrix[i][j];
                while(true){
                    int s = n-1-x, t = y;
                    if(visited[t][s] == 1) break;
                    int temp = matrix[t][s];
                    matrix[t][s] = value;
                    value = temp;
                    visited[t][s] = 1;
                    x = t;
                    y = s;
                }
            }
        }
    }
}

Solution 2

此方法类似Solution 1，但是并非原地算法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] mat = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int s = n-1-i, t = j;
                mat[t][s] = matrix[i][j];
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = mat[i][j];
            }
        }
    }
}

Solution 3

辅助方法getPixel计算旋转后的像素位置。
旋转时候矩阵内的四个分区的像素会互相替换。
因此需要将需要旋转的初始位置记录进入队列。
旋转图像时根据getPixel方法计算出需要替换的位置。
然后依次替换像素。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        Queue<Integer> queue = new LinkedList();
        for (int p = 0; p < n/2; p++){
            for(int q = 0; q < (n+1)/2; q++){
                queue.offer(p * n + q);
            }
        }

        while(!queue.isEmpty()){
            int i = queue.poll();
            int INDEX = i;
            boolean flag = true;
            int temp = matrix[i/n][i%n];
            while(i != INDEX || flag ){
                flag = false;
                int j = getPixel(n, i);
                int swap = matrix[j / n][j % n];
                matrix[j / n][j % n] = temp; 
                temp = swap;
                i = j;
            }
        }     
    }
    
    private int getPixel(int n, int o){
        int row = o / n;
        int col = o % n;
        int newRow = col;
        int newCol = n - (row + 1);
        return (newRow * n) + newCol;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 256 words)

153. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

二分搜索，寻找断裂点。
当left小于right时循环。
每次计算出mid，分为两种情况：

  • 如果nums[mid]小于nums[nums.length-1]，则右半侧为顺序的。
  • 反之则左半侧为顺序，右半侧为无序的。
    以此来更新搜索范围。
    由于mid计算公式向下取整。
    当更新left时更新为mid+1，向前一格。
    当更新right时更新为mid。
    最后返回nums[left]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findMin(int[] nums) {
        return findBreakPoint(nums,0,nums.length-1);
    }
    
    private int findBreakPoint(int[] nums, int left, int right){
        while(left < right){
            int mid = (right - left)/2 + left;
            if(nums[mid] < nums[nums.length-1]){
                right = mid;
            }
            else if(nums[mid] >= nums[0]){
                left = mid+1;
            }
            
        }
        return nums[left];
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 295 words)

75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

快速排序是原地排序，因此此问题可以采用快速排序解决。

选择left上的元素pivot，设置一个指针index为left+1。
遍历left+1至right的数组，如果遍历的值小于pivot则将nums[i]与nums[index]交换，然后将index向右移动。

因此index左侧的元素均小于pivot，index右侧的元素均大于pivot。
最后将nums[index]与pivot交换，此时pivot左侧元素均小于它，右侧元素均大于它，因此index不需要再动。
然后分别向下递归left至index-1，index+1至right。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public void sortColors(int[] nums) {
        quickSort(nums, 0, nums.length-1);
    }
    
    private void quickSort(int[] nums, int left, int right){
        if( right - left < 1 ){
            return;
        }
        int pivot = nums[left];
        int index = left+1;
        for(int i = index; i <= right; i++){
            if(nums[i] < pivot){
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                index++;
            }
        }
        index--;
        
        nums[left] = nums[index];
        nums[index] = pivot;
        
        quickSort(nums,left,index-1);
        quickSort(nums,index+1,right);
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 303 words)

33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

二分搜索，二分后将会形成两个区间，一个区间是顺序的，另一个是无序的。
如果target等于中间值则返回。
分别处理两种情况下移动指针的方式。
当顺序区间在左半边时：
当target在顺序区间内，则更新右指针的位置。
否则更新左指针位置。
当顺序区间在右半边时：
当target在顺序区间内，则更新左指针的位置。
否则更新右指针位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length-1;
        
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target){
                return mid;
            }
            
            if( nums[mid] >= nums[0] ){
                if(target >= nums[0] && target < nums[mid] ){
                    right = mid - 1;
                }
                else{
                    left = mid + 1;
                }
            }
            else{
                if(target > nums[mid] && target <= nums[nums.length-1]){
                    left = mid + 1;
                }
                else{
                    right = mid -1;
                }
            }

        }
        return -1;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 355 words)

15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

三数之和，重点是如何遍历后去除重复的数组。
首先对数组进行排序。
遍历数组，三个数中最小的数字为nums[i]。
此时需要去除重复的nums[i]。如重复则继续下一次循环。
此时设置双指针left和right，分别在nums[i]右侧的子数组的首尾。

  • 当nums[i] + nums[left] + nums[right] > 0时，后两个数的和需要减小，right指针向左移动。
  • 当nums[i] + nums[left] + nums[right] < 0时，后两个数的和需要增大，left指针向右移动。
  • 当nums[i] + nums[left] + nums[right] = 0时，找到一个组合。
    此时需要去除重复的nums[left]和nums[right]。如重复则更新left或right的指针。
  • 将组合添加到返回列表。

最后返回列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length; i++){
            int left = i+1;
            int right = nums.length-1;
            if(i>0 && nums[i] == nums[i-1]){
                continue;   
            }
            
            while(left < right){
                if(nums[i]+nums[left]+nums[right]==0){
                    while(left+1 < nums.length && nums[left] == nums[left+1]){
                        left++;
                    }
                    while(right-1 > i && nums[right] == nums[right-1]){
                        right--;
                    }
                    List<Integer> list = new ArrayList();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    ans.add(list);
                    
                    left++;
                    right--;
                }
                else if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return ans;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 315 words)

34. Find First and Last Position in Sorted Array

问题
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

二分搜索，搜索中间项。
中间项等于左侧和右侧指针的中点，根据搜索左侧边界和右侧边界选择二分向下舍去或是二分向上补足。
当中间项小于目标，则更新左侧边界。
若中间项大于目标，则更新右侧边界。
当中间项等于目标时，根据搜索左侧边界还是右侧边界选择更新左侧或右侧。
由于有可能有重复元素存在，因此需要继续二分搜索下去，直到右侧边界大于左侧边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{searchLeft(nums,target),searchRight(nums,target)};
    } 

    private int searchRight(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                left = mid+1;
            }
        }
        return result;
    }
    
    private int searchLeft(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left+1)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                right = mid-1;
            }
        }
        return result;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 243 words)

538. Convert BST to Greater Tree

问题
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

  • 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

DFS搜索，设置一个成员变量记录上一个节点的值。
先递归右侧节点。
设置当前节点的值为自身的值加上temp中的值。
更新temp中的值，再递归左侧节点。


class Solution {
    int temp;
    public TreeNode convertBST(TreeNode root) {
        temp = 0;
        dfs(root);
        return root;
    }
    
    private void dfs(TreeNode root){
        if(root == null){
            return;
        } 
        dfs(root.right);
        root.val += temp;
        temp = root.val;
        dfs(root.left);
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 291 words)

669. Trim a Binary Search Tree

问题
Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

DFS搜索，每次递归带上搜索的范围值。
如果当前节点小于搜索范围，递归当前节点的右子节点。
反之递归当前节点的左子节点。
如果当前节点在搜索范围中，则其左子节点等于递归后的左子节点，右子节点等于递归后的右子节点。
然后返回当前节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null){
            return null;
        }
        if(root.val < low){
            return trimBST(root.right, low, high);
        }
        if(root.val > high){
            return trimBST(root.left, low, high);
        }
        
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 276 words)

701. Insert into a Binary Search Tree

问题
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.

如果root为空则将值直接添加到根节点。
辅助方法比较当前节点的值。
如当前值大于添加的值，则检测左子节点是否为空。
如不为空则递归左子节点。
如当前值小于添加的值，则检测右子节点是否为空。
如不为空则递归右子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null){
            root = new TreeNode(val);
        }
        insert(root,val);
        return root;
    }
    
    private void insert(TreeNode root, int val){
        if (root.val < val){
            if (root.right == null){
                root.right = new TreeNode(val);
            }
            insert(root.right, val);
        }
        else if (root.val > val){
            if (root.left == null){
                root.left = new TreeNode(val);
            }
            insert(root.left, val);
        }
        return;
    }
}
Follow

Recents

Archives

Links

×