Trees6 Blind 75 | Validate Binary Search Tree (Trees 7 / 11) 알고리즘 두 가지 풀이가 있는데 현재 노드가 left보다 크고 right보다 작은지 확인하는 것과 직접 left로 가서 left의 val이 내려 가기 전의 노드보다 작은지 확인하는 방법이 있다. 두 번째 방법으로 풀이를 해볼건데 중요한 점은 지금까지 봐왔던 값들중 최소 값 최대 값을 변수로 따로 지정하여 비교해가며 검사해야한다. 구현 구현을 하다 막히고서 BST의 정의를 복습하게 해준 좋은 문제다. 2023. 6. 28. Blind 75 | Lowest Common Ancestor of a Binary Search Tree (Trees 5 / 11) 알고리즘 BST인 문제일 때에는 값을 비교하며 left로 갈지 rgiht으로 갈지 생각하면 된다 첫 예시의 경우 만약 p = 0, q = 4라 가정하면 둘 다 6보다 작기에 left로 간다 p = 7, q = 9라 가정하면 둘 다 6보다 크기에 right으로 간다. 만약 둘다 작거나 크지 않다면 그 사이에 있다는 뜻이므로 그대로 리턴한다. 예시 2에서와 같이 root이 2라 p라서 같은 경우도 컨디션에서 안 걸리기 때문에 그대로 리턴될 수 있도록 구현한다. 구현 2023. 6. 22. Blind 75 | Subtree of Another Tree (Trees 4 / 11) Same Tree 문제의 다음 버전으로 root 안에 subRoot과 동일한 트리가 있는지 확인하는 문제다. bfs를 이용한 풀이 재귀를 이용한 풀이 2023. 6. 21. Blind 75 | Same Tree (Trees 3 / 11) 풀이 두 개의 트리가 완전히 동일한 트리인가 확인하는 문제다. 재귀를 이용하며 베이스 케이스로는 3개를 둔다. 15줄 = p는 있는데 q가 null일 경우, p가 null인데 q는 있는 경우 같은 트리가 아니므로 false 16줄 = p와 q 둘 다 null 일 경우 같은 트리이므로 return 17줄 = p와 q의 값이 다른 경우 false를 리턴 위의 모든 조건이 클리어되면 p와 q의 값이 같은 것임으로 true를 리턴하고 동시에 AND operator와 함께 left, right에 함수를 호출해 주면 깔끔하게 풀 수 있다. 훨씬 쉬운 풀이는 정답인 것만 체크하고 나머지 컨디션들이 걸리면 false로 리턴한다. p나 q가 undefined여서 런타임 오류가 날 것을 대비해 p && q 를 넣어 먼저 .. 2023. 6. 20. Blind 75 | Maximum Depth of Binary Tree (Trees 2 / 11) 풀이 재귀를 이용해서 쉽게 풀 수 있다. 베이스 케이스는 노드가 null 일 때를 가정하고 0을 리턴한다. 한번 재귀를 할때마다 1씩 더 추가돼서 리턴되며 왼쪽 오른쪽 노드에 재귀로 함수를 호출하고 그중 높은 값을 받으면 된다. 2023. 6. 20. Blind 75 | Invert Binary Tree (Trees 1 / 11) 풀이 재귀를 이용한 풀이와 bfs iterative 풀이가 있다. 둘 다 베이스 케이스를 잘 고려하는 게 관건이다. 딱히 해설이 필요 없는 풀이로 왼쪽 오른쪽을 바꿔주기만 하면 된다! 2023. 6. 20. 이전 1 다음
