반응형 Algorithm66 235 : Lowest Common Ancestor of a Binary Search Tree ( leetcode / java ) * 해결과정 제목에 이진탐색 트리라고 써있습니다. 이를 적극적으로 활용합니다! (하지만 저는 또 그냥 지나쳤습니다.. ㅜㅜ) 또한 최소 공통 조상에 대한 문제이기도 합니다. 하지만 걱정하지 않아도 되는 것은 이진탐색 트리이기 때문에, 또한 p,q가 동시에 주어졌기 때문에 간단하게 해결 할 수 있습니다. 각 해당 노드의 값의 대소비교를 통해 해결합니다. class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { int parentVal = root.val; int pVal = p.val; int qVal = q.val; if(pVal>parentVal && qVal>parentVal) return.. 2020. 10. 30. 993 : Cousins in Binary Tree ( leetcode / java ) *해결과정 우리가 필요한 것은 depth(깊이), parent(부모)이다. 새로운 배열을 만들어서 DFS순회를 돌면서 depth와 parent를 갱신하면 된다. 굳이 새로운 class를 만들 것 없이 매개변수로 전달하면 된다. class Solution { int xDepth=0; int yDepth=0; int xParent = 0; int yParent = 0; public boolean isCousins(TreeNode root, int x, int y) { DFS(root,x,y,0,-1); return (xDepth==yDepth) && (xParent!=yParent); } public void DFS(TreeNode root, int x, int y, int depth,int parent){.. 2020. 10. 30. 1662 : 압축 ( 백준 / java ) * 해결 과정 이 문제는 압축이 문자열 길이라는 것에 주의해야 하며, 대부분의 문자열을 다루는 것은 stack을 통해서 해결해야 합니다. 더불어 재귀를 이용하여 괄호를 처리하는 스킬을 배울 수 있습니다. public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); line = sc.next(); Stack stack = new Stack(); reverse = new int[50]; for(int i=0;i 2020. 10. 29. 16926 배열돌리기1, 16927 배열돌리기2 ( 백준 / java ) www.acmicpc.net/problem/16921 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← .. 2020. 10. 29. 606 : Construct String from Binary Tree ( leetcode / java ) *해결과정 앞에 문제가 이진탐색트리인데 제대로 살펴보지 않았기 때문에 이제 꼭 어떤 트리종류인지를 확인한다!! 아쉽게도 이번에는 아무 트리도 아니다 ㅋㅋ 순회하면서 괄호를 포함시키는 문제이다. 특이한 점은 Example 2에서 왼쪽 괄호가 null 일 때는 ()를 반환해야 한다는 것이다. 간단하게 조건문을 걸어 재귀로 해결한다. class Solution { public String tree2str(TreeNode t) { if(t==null) return ""; String line = t.val+""; if(t.left!=null) { line += "(" + tree2str(t.left) + ")"; } if(t.left==null && t.right!=null) { line +="()"; } if.. 2020. 10. 29. 669 : Trim a Binary Search Tree ( leetcode / java ) *해결과정 이진 탐색트리라는 것에 주의한다. 특징으로는 root값은 왼쪽 자식보다 값이 크고 오른쪽 자식보다는 값이 작아야 한다. 이 특징을 이용해 low와 high가 주어졌을 때 유동적으로 이동해야 한다. 이진 탐색트리라는 특성을 제대로 파악하지 못해서 문제푸는데 많은 어려움을 겪었다. 즉, root값이 low값보다 작으면 너무 작은 값이므로 오른쪽 자식으로 이동하고 root값이 high보다 크면 너무 크기 때문에 왼쪽 자식으로 이동한다. class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null) return root; if (root.val > high) return trimBST(root... 2020. 10. 29. 637 : Average of Levels in Binary Tree ( leetcode / java ) *해결 과정 각 depth 별로 list를 만들고 저장하는 방법이 있고, BFS로 같은 level을 순회하면서 값을 계산하는 방법이 있다. 1. List 이용 2. LinkedList를 통해 BFS를 이용 *1번 방법 class Solution { List list = new ArrayList(); public List averageOfLevels(TreeNode root) { if(root==null) return null; DFS(root,0); List doubleList = new ArrayList(); for(List integerList : list){ int size = integerList.size(); double sum=0; for(int val : integerList ){ sum+=.. 2020. 10. 28. 872 : Leaf-Similar Trees ( leetcode / java ) *해결과정 List를 2개 만들고, DFS를 2번 돌려서 List를 비교한다. list를 비교할 때 equals를 써서 비교가 가능하다. import java.util.*; class Solution { public boolean leafSimilar(TreeNode root1, TreeNode root2) { List list1 = new ArrayList(); List list2 = new ArrayList(); DFS(root1, list1); DFS(root2, list2); return list1.equals(list2); } public void DFS(TreeNode root, List list){ if(root.left==null && root.right==null){ list.add(ro.. 2020. 10. 28. 965 : Univalued Binary Tree ( leetcode / java ) *해결 과정 단일 tree를 찾는 것이 핵심이다. 마찬가지로 void DFS()함수로 매 순간 비교하면서 값이 달라지면 boolean값을 업데이트하는 방법과 계속 초기 함수에서 재귀를 돌면서 정답을 찾는 방식이 있다. *1번 class Solution { boolean isSame=true; public boolean isUnivalTree(TreeNode root) { if(root==null) return false; int val = root.val; DFS(root, val); return isSame; } public void DFS(TreeNode root, int val){ if(root.val != val) { isSame=false; return; } if(root.left!=null) .. 2020. 10. 28. 이전 1 2 3 4 5 6 7 8 다음 반응형
