JJJ

https://leetcode.com/problems/symmetric-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 boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }
    
    public boolean check(TreeNode leftNode, TreeNode rightNode) {
        
        if(leftNode == null && rightNode == null) {	// 둘다 자식node가 없으면 true
            return true;
        }
        
        if(leftNode == null || rightNode == null) {	// 한쪽만 자식node가 없으면 false
            return false;
        }
        
        if(leftNode.val != rightNode.val) {	// 값이 서로 다르면 false
            return false;
        }
        
        // 내려가면서 계속 확인
        return check(leftNode.left, rightNode.right) && check(leftNode.right, rightNode.left);       
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42883

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        
        char[] numbers = number.toCharArray();
        int digit = number.length() - k;	// 자릿수
        
        int i = 0;	// 탐색범위 시작
        int j = numbers.length - digit;	// 탐색범뉘 끝
        
        while(j < numbers.length) {
        	int max = -1;	// max = 0 으로 하면 배열에 0만 있는 경우 최대값 추출 불가능
        	int index = 0;
        	for (int n = i; n <= j; n++) {	// 추출대상 구간의 최대값 + 인덱스
        		if(numbers[n] - '0' == 9) {	// 9면 무조건 최대이므로 break
        			max = 9;	
					index = n;
					break;
        		}        		
				if(numbers[n] - '0' > max) {
					max = numbers[n] - '0';	
					index = n;
				}
			}        
        	answer.append(numbers[index]);	// 결과 기록
            
        	i = index + 1;	// 탐색 범위 변경
        	j++;
        }
        return answer.toString();
    }
}

- 7자리의 수에서 3개를 제거하면 결과는 4자리의 수임

- 최초의 순서는 유지해야 하므로, 맨 앞 자릿수부터 후보가 되는 범위를 찾고, 그 범위 안에서 최댓값을 고르면 됨

- 다음 순번에는 선택된 숫자 다음부터 시작해서 탐색을 시작

https://programmers.co.kr/learn/courses/30/lessons/42885

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 1;
        int rest = limit;
        int i = 0;	// 가장 가벼운 사람
        int j = people.length - 1;	// 가장 무거운 사람
        
        Arrays.sort(people);	
        
        while(i <= j) {
        	if(rest >= people[i] + people[j]) {
        		rest -= people[i] + people[j];
        		i++;
        		j--;
        	} else if (rest >= people[j]) {
        		rest -= people[j];
        		j--;
        	} else if (rest >= people[i]) {
        		rest -= people[i];
        		i++;
        	} else {
        		answer++;
        		rest = limit;
        	} 	
        }
        
        
        return answer;
    }
}

1) 가장 가벼운 사람 + 가장 무거운 사람 2명을 태울 수 있으면 태워본다.

2) 1)이 불가능이면, 무거운 사람을 태운본다.

3) 2)가 불가능이면, 가벼운 사람을 태워본다. 

4) 3)도 불가능하면, 새로운 보트를 구해온다.

처음엔, 그냥 가벼운 사람부터 or 무거운 사람부터 차례로 태워보내면 되는줄 알았는데, 아니었음...

https://programmers.co.kr/learn/courses/30/lessons/43165

class Solution {
    public int solution(int[] numbers, int target) {        
        int answer = 0;
        
        int result1 = dfs(numbers, numbers[0], target, 1);
        int result2 = dfs(numbers, -numbers[0], target, 1);
        answer = result1 + result2;        
        return answer;
    }
	
	public int dfs(int[] numbers, int sum, int target, int i) {
		
		int result = 0; 
		
		if(i == numbers.length) {	// 배열 마지막 인덱스 까지 같을때
			if(sum == target)	// 합계가 target과 같으면 +1
				return 1;
			else
				return 0;
		}
		
		result += dfs(numbers, sum + numbers[i], target, i+1);	// 양수
		result += dfs(numbers, sum - numbers[i], target, i+1);	// 음수
		return result;
	}	
}

- dfs는 재귀로도 구현이 가능하고, 스택을 사용해서도 구현이 가능함

- 재귀 함수는 항상 재귀를 끝내는 부분과 재귀 호출을 하는 부분으로 나뉜다.

- 재귀 함수안에서는 반복문은 X

- 아래와 같이 재귀적으로 반복된다고 생각하면 됨 : 재귀 호출하면서 마지막 노드(i == numbers.length)까지 갔을때 합계(sum)가 target과 같으면 +1 카운팅

https://programmers.co.kr/learn/courses/30/lessons/43162

- 네트워크 하나를 그래프 하나라고 생각하면 된다.

- computer 이차원 배열에 존재하는 그래프의 개수가 네트워크의 개수임

- BFS/DFS 탐색은 하나의 그래프를 탐색하는 것이므로, 탐색이 끝났다면 모든 node들이 방문이 되어야 함, 하지만 트리가 여러개인 경우, 하나의 그래프 탐색을 했다하더라도, 방문하지 않은 node들이 있을 수 있다. 

1. 재귀를 활용한 DFS

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        boolean[] visit = new boolean[computers.length];
        
        // dfs가 끝났는데 방문하지 않은 노드가 있다면 네트워크가 더 있음
        for (int i = 0; i < computers.length; i++) {
            if(!visit[i]){
            	answer++;   
                dfs(i, visit, computers);			    
            }			
		}
        return answer;
    }
    
    public void dfs(int node, boolean[] visit, int[][] computers) {
		visit[node] = true;
		
		for (int next = 0; next < computers.length; next++) {
			if(node != next && !visit[next] && computers[node][next] != 0) {
				dfs(next, visit, computers);
			}
		}
    }
}

2. 큐를 활용한 BFS 풀이

import java.util.*;

class Solution {
    public static int solution(int n, int[][] computers) {
        int answer = 0;               
        boolean[] visit = new boolean[computers.length];
    	Queue<Integer> queue = new LinkedList<Integer>();
                
        for (int i = 0; i < computers.length; i++) {
            if(!visit[i]){
            	answer++;
                bfs(i, visit, computers, queue);			    
            }
		}        
        return answer;
    }
    
    private static void bfs(int node, boolean[] visit, int[][] computers, Queue<Integer> queue) {
    	queue.offer(node);
    	
		while(!queue.isEmpty()) {
			int com = queue.poll();
			visit[com] = true;
			
			for (int next = 0; next < computers.length; next++) {
				if(com != next && !visit[next] && computers[com][next] != 0) {
					queue.offer(next);
				}
			}
		}
	}
}

/**
 * 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 result = 0;
    
    public int maxDepth(TreeNode root) {
        dfs(root, 1);
        return result;
    }
    
    public void dfs(TreeNode node, int depth) {
        if(node == null) {            
            return ;
        }
        
        if(node.left == null && node.right == null) {
            result = Math.max(result, depth);
        }
        
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
}

- 레벨 별로 별도의 list에 담기 위해서 queue사이즈 만큼 돌리는 for 사용

- 그냥 levelorder순회는 for안써도됨

/**
 * 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 {
    List<List<Integer>> resultList = new ArrayList<List<Integer>>();
	
	public List<List<Integer>> levelOrder(TreeNode root) {
		levelOrderBFS(root);
		return resultList;        
    }
	
	public void levelOrderBFS(TreeNode root) {        
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		if(root != null) {
                queue.add(root);	// 최초 root 노드 넣기

                while(!queue.isEmpty()) {
                    List<Integer> levelList = new ArrayList<Integer>();
                    int size = queue.size();

                    // 레벨 순회
                    for (int i = 0; i < size; i++) {
                        TreeNode node = queue.poll();	// 큐에서 꺼내기
                        levelList.add(node.val);	// 레벨 list에 담기				

                        // 인접 노드를 큐에 넣기
                        if(node.left != null) queue.offer(node.left);
                        if(node.right != null) queue.offer(node.right);
                    }
                    resultList.add(levelList); // 결과 List에 레벨 list 담기
                }	
            }
	}
}

1. Preorder

/** * 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 { List<Integer> list = new ArrayList<Integer>(); public List<Integer> preorderTraversal(TreeNode root) { preOrder(root); return list; } public void preOrder(TreeNode root) { if(root != null) { list.add(root.val); preOrder(root.left); preOrder(root.right); } } }

2. InOrder

/** * 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 { List<Integer> list = new ArrayList<Integer>(); public List<Integer> inorderTraversal(TreeNode root) { inorder(root); return list; } public void inorder(TreeNode root) { if(root != null) { inorder(root.left); list.add(root.val); inorder(root.right); } } }

3. Postorder

/** * 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 { List<Integer> list = new ArrayList<Integer>(); public List<Integer> postorderTraversal(TreeNode root) { postorder(root); return list; } public void postorder(TreeNode root) { if(root != null) { postorder(root.left); postorder(root.right); list.add(root.val); } } }

이건..무식하게 푼 것

/** * 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 parent = null; int flag = -1; public TreeNode deleteNode(TreeNode root, int key) { TreeNode result = delete(root, key); return result; } private TreeNode delete(TreeNode root, int val) { if(root == null) return null; if(root.val > val) { // 왼쪽으로 parent = root; flag = 1; delete(root.left, val); } else if (root.val < val) { // 오른쪽으로 parent = root; flag = 0; delete(root.right, val); } else { // 삭제할 Node를 찾음 if(root.left == null && root.right == null) { // 1) 자식 Node 없음 if(flag == 0) parent.right = null; else if(flag == 1) parent.left = null; else root = null; return root; } else if (root.left != null && root.right == null) { // 2) 자식 Node 1개 (left) if(flag == 0) parent.right = root.left; else if(flag == 1) parent.left = root.left; else root = root.left; return root; } else if (root.right != null && root.left == null) { // 2) 자식 Node 1개 (right) if(flag == 0) parent.right = root.right; else if(flag == 1) parent.left = root.right; else root = root.right; return root; } else { // 3) 자식 Node 2개 TreeNode chgNode = findMin(root.right); int tmp = root.val; root.val = chgNode.val; chgNode.val = tmp; parent = root; flag = 0; delete(root.right, tmp); return root; } } return root; } private TreeNode findMin(TreeNode node) { while(node.left != null) { node = node.left; } return node; } }

/** * 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 deleteNode(TreeNode root, int key) { if(root == null) return null; if(key < root.val){ root.left = deleteNode(root.left, key); }else if(key > root.val){ root.right = deleteNode(root.right, key); }else{ if(root.left == null){ return root.right; }else if(root.right == null){ return root.left; }else{ int minVal = findMin(root.right); root.val = minVal; root.right = deleteNode(root.right, minVal); } } return root; } private int findMin(TreeNode root){ while(root.left != null){ root = root.left; } return root.val; } }

/**
 * 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 parent = null;
    int flag = -1;
    
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode result = insert(root, val);	        
		return result;
    }
	
	private TreeNode insert(TreeNode root, int val) {        
        
		if(root == null) {	// 최초에 빈 BST or 리프블록까지 온 경우
			root = new TreeNode(val);  // 신규 Node
            		if(flag == 0) parent.right = root;	// 오른쪽에 insert
            		if(flag == 1) parent.left = root;	// 왼쪽에 insert
            		return root;
		}
		if(root.val < val) {	// 오른쪽
            		flag = 0;
            		parent = root;
			insert(root.right, val);
        }
		else if (root.val > val) {	// 왼쪽
            		flag = 1;
            		parent = root;
			insert(root.left, val);
        }
		
		return root;
	}
}

다시 푼거

/**
 * 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) {  // 빈 트리면 루트 노트로 삽입
            return new TreeNode(val);            
        }               
        
        if(root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        
        if(root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        
        return root; 
    }
}

BST 삽입/삭제 참고 => https://youtu.be/xxADG17SveY