[leetcode] 1028. Recover a Tree From Preorder Traversal

문제 : https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/

---

탐색은 preorder로 왼쪽을 다채우고 부모노드로 올라가고 나서는 값을 채우기 위해 왼쪽 자식트리로 내려가지 않는다.

TreeNode 구조체는 자식 노드의 정보만 담고 있으므로 부모노드를 저장하는 스택을 하나 만들었다.

 

pair<int, int> getValAndDepth(string& s) {
	if (s.size() == 0)	return { -1, -1 };
	
    int ind = 0;
	int val = 0;
	int depth = 0;
	for (; ind<s.size(); ind++) {
		if (s[ind] == '-') {
			if (val > 0) {
				ind--;
				break;
			}
			else depth++;
		}
		else {
			val *= 10;
			val += s[ind] - '0';
		}
	}
	s.erase(0, ind + 1);
	return { val, depth };
}

문자열에서 depth와 val를 분리한다.

좀 원시적으로 분리했는데 이보다 좋은 방법이 있는지는 찾아봐야겠다.

 

새로운 노드를 생성해서 값을 세팅할 때는 부모노드와 연결해야 하므로 새로 생성될 depth보다 1이 작은 depth의 노드를 찾는다. 

if (nowNode == NULL) { // 부모노드가 빈 경우 -> 루트
	root = newNode;
}else if (nowNode->left == NULL) { // 왼쪽 자식 노드가 없는 경우 -> 왼쪽 자식 노드
	nowNode->left = newNode;
}else { // 오른쪽 자식 노드
	nowNode->right = newNode;
}

적절한 자리를 찾았다면 위 3가지 경우에 맞춰 트리와 새로 생성한 노드를 연결한다.

if (nowDepth < depth) {
	// should go right child
} else {  // nowDepth > depth
	// should up
}

만약 적절한 자리(nowDepth+1 == depth) 가 아닌 경우 이동한다.

만약 현재 탐색 중인 depth가 새로운 depth 보다 작다면 오른쪽 노드로 탐색하면서 적절한 자리를 찾는다.

왜 왼쪽 노드는 탐색안하는가? 는 preorder이기 때문에 왼쪽 노드에 값이 들어가는 경우는 적절한 자리가 계속된다.(preorder는 왼쪽 노드를 먼저 탐색하기 때문에 더 이상 왼쪽 노드에 들어가지 않는 경우만 위 코드가 실행된다.)

탐색 중인 depth가 새로운 depth보다 크다면 부모노드를 탐색한다. 이 때 부모노드를 알기 위해 stack에 부모노드의 정보를 가지고 있어야 한다.

---

소스코드 : https://gist.github.com/fpdjsns/f366f0b70cda690516b8708ece8126e9

[leetcode] 1028. Recover a Tree From Preorder Traversal : https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/

 

다른 사람들 코드는 짧던데 탐방 좀 해봐야겠다.