Algorithm (66) 썸네일형 리스트형 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.. 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... 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+=.. 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.. 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) .. 559 : Maximum Depth of N-ary Tree ( leetcode / java ) *해결 과정 먼저 기본적으로 주어진 Node 의 형태를 확인해보자. N차 노드이기 때문에 자손이 List로 선언되었다는 것에 유의한다. 특히 우리는 depth를 구해야 하는데, Node에는 depth 변수가 선언되있지 않기 때문에 별도의 변수 선언이 필요하다. 여기서 해결 방안은 2가지이다. 1. 새로운 class를 만들어 depth를 추가한다. 2. depth에 대한 전역변수를 만들고 계속 업데이트하면서 값을 구한다. *1번 class Point{ Node node; int depth; public Point(Node node, int depth){ this.node=node; this.depth=depth; } } class Solution { int ans=0; public int maxDepth(.. 897 : Increasing Order Search Tree ( leetcode / java ) *해결 과정 모든 Tree를 순회하고, 오른쪽 트리만 계속 만들면 된다. 나는 ArrayList를 사용하고 get()을 통해 순회하였다. 여러가지 해설을 찾아보니 LinkedList로 선언하고 remove로 제거하면서 while에서 해결하는 것도 괜찮은 방법이라 생각한다. *ArrayList 사용 import java.util.*; class Solution { List list = new ArrayList(); public TreeNode increasingBST(TreeNode root) { DFS(root); Collections.sort(list); TreeNode node = new TreeNode(list.get(0)); list.remove(0); makeTree(node, 0); retur.. 700 : Search in a Binary Search Tree ( leetcode / java ) *해결 과정 void를 통한 함수를 사용하는 것과 TreeNode를 통한 함수를 사용하는 방법 2개가 있다. class Solution { TreeNode tree = null; public TreeNode searchBST(TreeNode root, int val) { DFS(root,val); return tree; } public void DFS(TreeNode root, int val){ if(root.val==val) { tree=root; return; } if(root.left!=null) searchBST(root.left,val); if(root.right!=null) searchBST(root.right,val); } } class Solution { public TreeNode sea.. 이전 1 ··· 3 4 5 6 7 8 9 다음
