LeetCode Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/
Binary Search Tree 를 탐색해서 가장 작은 값부터 return 하는 프로그램이다.

이것은 맨 위의 node 가 중간 값을 가져가고, left 는 그보다 작고, right 는 그보다 큰 값들이 저장되어 있다. 빠지지 말아야 할 함정이 Level 0 의 node 가 20 이고 Left 가 15, Right 30 Level 1 의 Right 가 Level 0 의 node 보다 커서는 안된다는 것이다. 그 생각을 해보면 풀기 쉽다.

아이디어는 이렇다. inOrder 로 트리를 탐색하면서 stack 에 값을 쌓는 것이다. 단, 보통의 inOrder 처럼 Left, Root, Right 순이 아니라, Right, Root, Left 순. 트리를 읽게 되면 최우하단(제일 큰 값 부터) 읽어서 stack 맨 위에는 제일 작은 값이 있게 될 것이다.

LeetCode Invert Binary Tree

바이너리 트리의 좌우를 바꾸는 것이다. 음.. 테스트 상으로는 recursive 보다 iterative 쪽이 조금 더 느리게 나왔다. iterative 방법으로는 inorder 방법으로 읽으면서 stack.push 한 후에, 다시 inorder 탐색을 하면서 stack.pop 하면서 넣을 계획이었는데, 첫번 째 탐색 때 tree의 cursor 가 맨 밑에 가 있는 것을 어떻게 처음으로 되돌릴 수 있을 것인가에 생각이 잘 안떠올라서, 솔루션 대로 swap 을 이용한 방법을 했다. 트리 탐색을 한번만 하는 것이니 좋을 거 같기도 하다.
Tree 문제에서는 트리 탐색이 제일 시간이 오래 걸리는 거겠지.

LeetCode Binary Tree Inorder Traversal

LeetCode 에 있는 Binary Tree Inorder Traversal

preorder 보다는 생각하는게 복잡했다. recursive 일 때는 쉬운데, iterative 로 하려니 stack을 써야 했고, stack 에 넣었다 뺄 때 하는 것이 preorder 과 달라서 살짝 머리가 아팠다. 

LeetCode. Binary Tree Preorder Traversal. Recursive

LeetCode Number of 1 bits

LeetCode 를 풀고 있는데, 숫자를 입력 받아서 bit에서 1이 몇개 나오는지 계산하는 문제를 풀고 있다. hamming weight 쉬울거라 생각했는데 답이 잘 안나오네 오답이라고 나오는 것들은 내 컴터(JDK 1.7) 에서는 잘 되는데... 뭐가 맞지 않는걸까..

뭐지.. 6번 라인 1일 때랑 0이 아닐때의 값이 다르다. 비트연산을 하는 것이다 보니 -1이 나오는걸까...

Cracking Coding Interview, LinkedLIst 로 Stack 구현하기

Stack 은 보통 배열을 이용하거나 하는데, LinkedLiest 를 이용하면 넣을 수 있는 양의 제한이 없어지게 된다. 배열의 사이즈를 가변적으로 변경할 수 있다면 얘기가 다르겠지만, Java 에서는 그게 되지 않는다. 그리고, 많이 들어가지도 않을 Stack을 위해 array의 크기를 크게 잡아놓는 것은 좋지 않다. LinkedList 는 검색이 좀 느릴 수도 있지만, 어차피 stack 은 맨 위의 item만 하나씩 꺼내는 것이기 때문에 문제가 되지 않는다.

[LeetCode] SameTree

두개의 바이너리 트리가 주어졌을 때, 두개가 같은 트리인지 확인한다.

17번 라인을 p==q 만 확인했을 때에는 272ms 에, p==null && q==null 을 했을 때에는 288ms 가 걸린다. 연산이 늘어나서일까. 

아이디어는 간단하다. 만약에 p 와 q 의 val 가 같다면 재귀로 왼쪽 자식트리와 오른쪽 자식트리의 boolean 값을 비교한다. 그리고 p 와 q 가 null이 되는 순간이 올 것이다. (leaf node) 그럴 때 둘다 null 이라면 같은 것이니, return true.

true 가 되는 경우는 적으니, 일단 if 로 다 정리하고, 나머지는 else 로 return false 한다. 기본값도 return false

recursive 는 좀 생각하기 복잡할 때가 있는데 나도 한동안 이해가 엄청 안되서 recursive 를 거의 쓰지 않았었다. 근데 계속 하다보니 조금씩 익숙해진다.