728x90
leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/786/
이진 트리!!!! 이론을 공부해도 코드로 구현하기는 녹록치 않다 💬
30분동안 푼 내용..문제 해석하느라 정신이 없었다.
노드를 순회하는 순서와 재귀함수를 써서 반복해야 하는것은 알았지만 코드 정리가 안되고 헤매는 모습😅
메서드를 새로 생성해도 된다는 생각을 못하고 해당 메서드 안에서만 풀려고하니까 이래저래 더 꼬인듯하다.
public class BinaryTree0310 {
public List<Integer> inorderTraversal(TreeNode root) {
//순서대로 처음에 들어오는 root가 루트노드
//그 다음이 left
//그 다음이 right
//반복
List<Integer> list = new ArrayList<Integer>();
if(root!=null) {
//첫번째 배열 정렬
list.add(root.val);
//해당 루트로 새로 세팅 (?) 어디에서 세팅해야할까
TreeNode tree = new TreeNode(root.val);
}else if(root==null) {
}
//중위순회는 left - root - right 순으로 순회
//root가 정해질 때마다 왼쪽 값 있는지 확인
//있으면 먼저 정렬
return list;
}
}
결국 정답을 보고 이해해보기로 했다.
Pseudocode (수도코드)
inorder (node)
if node = null then return
inorder (node.left)
visit (node)
inorder (node.right)
➡ O(N0 한번 씩 모두 방문
class Solution {
public List < Integer > inorderTraversal(TreeNode root) {
List < Integer > res = new ArrayList < > ();
helper(root, res);
return res;
}
public void helper(TreeNode root, List < Integer > res) {
if (root != null) {
if (root.left != null) {
helper(root.left, res);
}
res.add(root.val);
if (root.right != null) {
helper(root.right, res);
}
}
}
}
스택을 활용해서 푸는 방법도 있었다.
public class Solution {
public List < Integer > inorderTraversal(TreeNode root) {
List < Integer > res = new ArrayList < > ();
Stack < TreeNode > stack = new Stack < > ();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
}
메서드를 만들지 않고 푸는 법
class Solution {
public List < Integer > inorderTraversal(TreeNode root) {
List < Integer > res = new ArrayList < > ();
TreeNode curr = root;
TreeNode pre;
while (curr != null) {
if (curr.left == null) {
res.add(curr.val);
curr = curr.right; // move to next right node
} else { // has a left subtree
pre = curr.left;
while (pre.right != null) { // find rightmost
pre = pre.right;
}
pre.right = curr; // put cur after the pre node
TreeNode temp = curr; // store cur node
curr = curr.left; // move cur to the top of the new tree
temp.left = null; // original cur left be null, avoid infinite loops
}
}
return res;
}
}
728x90
'코딩테스트' 카테고리의 다른 글
[LeetCode] 13. Roman to Integer (2) | 2021.03.12 |
---|---|
[LeetCode] 112. Path Sum (0) | 2021.03.11 |
[LeetCode] 509. Fibonacci Number (JAVA) (0) | 2021.03.08 |
How the DNS works (0) | 2021.03.07 |
[Codility] BinaryGap (JAVA) (0) | 2021.02.26 |