Trees and Graphs 2: Medium

Kth Smallest Element in a Binary Search Tree

/**
 * 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 int kthSmallest(TreeNode root, int k) {
        List<Integer> l = new ArrayList<Integer>();
        
        helper(root, l);
        
        return l.get(k - 1);
    }
    
    private void helper(TreeNode root, List<Integer> l) {
        
        if (root != null) {
            helper(root.left, l);
            l.add(root.val);
            helper(root.right, l);
            
        }
    }
}

BST니 왼쪽 < 중간 < 오른쪽인 법칙을 이용해서

왼 -> 중 -> 오 로 가주는 inorder을 사용해서 list를 만들어줌

그 후 kth element를 return

Inorder successor in BST

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        cur = None
        
        while (root):
            if p.val < root.val:
                cur = root
                root = root.left
            else:
                root = root.right
        
        return cur
            
        

전문제랑 비슷한거 같아서 이번엔 파이선으로 풀어봤읍니다

Number of Islands

class Solution {
    char[][] count;
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int count = 0;
        int h = grid.length;
        int w = grid[0].length;
        
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    helper(grid, i, j);
                }
            }
        }
        
        return count;
    }
    
    public void helper(char[][] grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == '0') {
            return;
        }
        grid[x][y] = '0';
        helper(grid, x - 1, y);
        helper(grid, x + 1, y);
        helper(grid, x, y - 1);
        helper(grid, x, y + 1);
    }
}

아일랜드~~