606. Construct String from Binary Tree [이진트리 전위 탐색]
Construct String from Binary Tree - LeetCode
문제 설명
원문
Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
번역
이진 트리의 루트가 주어졌을 때, 전위 순회 방식을 사용하여 이진 트리에서 괄호와 정수로 구성된 문자열을 생성하고 반환합니다.
문자열과 원래 이진 트리 사이의 일대일 매핑 관계에 영향을 주지 않는 빈 괄호 쌍은 모두 생략합니다.
Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)"
입력 : root = [1,2,3,4]
출력 : “1(2(4))(3)”
설명 : 원래는 1(2(4)())(3()()) 이지만 이진트리 사이의 1:1 매핑 관계 에 영향을 주지 않는 빈 괄호는 제거 한다는 룰이다.
- 1(2(4)())(3()())
- 4 이후에 방문한 2의 오른쪽 자식노드 () 생략
- 1(2(4))(3()())
- 2의 오른쪽 자식노드 이후에 방문한 3
- 3의 왼쪽 자식노드 () 생략
- 3의 오른쪽 자식노드 () 생략
⇒ 생략 규칙에 따라서 최종 정답은 이렇게 된다 : 1(2(4))(3)
여기서 내가 생각한 핵심은 방문하지 않는 노드라도 일단 () 를 찍어야 한다는 것이었다.
문제정의
- 이진트리, root 노드가 주어진다.
- 노드를 전위탐색 하는 코드를 작성하라.
- 전위탐색은
- 현재 노드 출력
- 왼쪽 자식 노드로 이동 → 1번으로
- 더이상 왼쪽 노드가 없다면 오른쪽 자식으로 이동 →1번으로
- 전위탐색은
- 자식 노드 탐색시, 현재 노드의 값을 찍기 전 ( 출력, 나올때 ) 출력 해야한다
- 루트노드는 ( ) 출력하지 않는다.
- 1 : 1 매핑 노드 일때는 ( ) 를 생략한다.
문제 형태
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public String tree2str(TreeNode root) {
}
}풀이
전위 탐색 코드
public static void preOrder(TreeNode node, StringBuilder answer) {
if(node != null){
answer.append(node.val);
preOrder(node.left, answer);
preOrder(node.right, answer);
}
}이진트리의 전위탐색 코드는 간단하다.
- 루트 노드의 값을 출력한다.
- 첫번째 재귀에따라서 왼쪽 노드의 Depth 끝까지 현재 노드의 값을 출력하면서 내려간다.
- 왼쪽 노드 탐색이 모두 끝나면, preOrder(node.right, answer); 을 통해 오른쪽 서브트리 안에서 또 왼쪽 노드들을 먼저 탐색한다.
node ≠ null 이 아닐때까지,
즉 모든 트리들을 탐색하게 된다.
1차 정답
class Solution {
public static void preOrder(TreeNode node, StringBuilder answer){
answer.append("(");
if(node != null){
answer.append(node.val);
if (node.left != null)
preOrder(node.left, answer);
if (node.right != null)
preOrder(node.right, answer);
answer.append(")");
}
}
public String tree2str(TreeNode root) {
StringBuilder sb = new StringBuilder();
preOrder(root, sb);
sb.deleteCharAt(0);
sb.deleteCharAt(sb.length()-1);
return sb.toString();
}
}- String 은 계속 객체를 만들고 지우므로, StringBuilder 를 통해 계속 문자열을 붙여줬다
- preOrder 함수에서, 일단 함수안에 들어오면 ( 나갈때는 ) 를 출력한다
- 하지만 루트는 괄호가 없어야 한다
- sb.deleteCharAt(0); 로 통해 루트 노드 앞의 ( 를 제거
- sb.deleteCharAt(sb.length()-1); 를 통해 루트노드 뒤의 ) 를 제거
처음에는 이렇게 작성하면 통과가 되었다. 첫번째 케이스에서는 통과가 된다.
그러나 두번째 케이스에서 실패한다.
두번째 케이스에서 위 코드대로 가면 틀린다.
중간 괄호가 없다고 한다.
여기서 문제에 제시된 1:1 매핑 노드가 무엇인지에 대해 알 필요가 있다.
이게 처음에는 무슨소린가 했다.
설명해보자면
전위 탐색은 왼쪽을 먼저 본다.
1번 예제처럼, 왼쪽 자식노드만 (4)만 있을때 는
2번 노드에서 오른쪽 자식을 방문했다는 출력 ( ) 를 출력을 생략할 수 있다.
그러나 왼쪽 그림에서 처럼
오른쪽 자식만 있는경우에는 2번 노드에서 왼쪽 자식노드 ( ) 를 방문했다는 출력을 생략하면 안된다.
⇒ 이게 1:1 매핑일땐 생략할 수 있다는 의미이다.
원문에는
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
이렇게 설명되어있다.
내가 생각했을땐, 소숫점을 표기할때 1.00100 을 표기한다고 하면 뒤에 0을 생략해서 1.001 로 표기할 수 있지만,
1.00100 의 앞의 소수점을 잘라서 1.100 으로 표기하면 다른숫자가 되는 뭐 그런건가부다 하고 생각했다.
최종
따라서 최종적으로는
public static void preOrder(TreeNode node, StringBuilder answer){
if(node != null){
answer.append("(");
answer.append(node.val);
if (node.left == null && node.right != null)
answer.append("()");
preOrder(node.left, answer);
preOrder(node.right, answer);
answer.append(")");
}
조건을 추가했다.
- 왼쪽노드는 없고, 오른쪽 노드는 있는경우에 왼쪽노드를 방문했다는 ( ) 출력을 넣어줬다.
문제에서 얘기하는 1:1 매핑 상황이라는 것은 오른쪽 자식노드만 있을때는,
왼쪽 자식이 없어도 방문했던 ( ) 표시를 남겨야 했다.
class Solution {
public static void preOrder(TreeNode node, StringBuilder answer){
if(node != null){
answer.append("(");
answer.append(node.val);
if (node.left == null && node.right != null)
answer.append("()");
preOrder(node.left, answer);
preOrder(node.right, answer);
answer.append(")");
}
}
public String tree2str(TreeNode root) {
StringBuilder sb = new StringBuilder();
preOrder(root, sb);
sb.deleteCharAt(0);
sb.deleteCharAt(sb.length()-1);
return sb.toString();
}
}내 생각
이진트리 탐색에 대한건, 예전 자료구조 스터디에서 배워보고 C++ 코드로 짜봐서 금방 나왔는데,
괄호 생략에 대해서 생각을 많이 했다.
1:1 매핑에 대한 설명을 이해 하고 어떨 때 괄호를 생략하고
어떨 때 아닌 건지 잘 모르겠었다.
if (node.left == null && node.right != null) answer.append("()");
이 수식을 알아내는게 좀 시간이 걸렸다.
많이 풀다 보면, 이런 규칙들도 금방 발견하겠지..?