Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal (C++)
EVEerNew 2023. 7. 4. 15:38문제
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
Construct Binary Tree from Preorder and Inorder Traversal - LeetCode
Can you solve this real interview question? Construct Binary Tree from Preorder and Inorder Traversal - Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same
leetcode.com
풀이
난이도: Medium
트리의 전위순회(preorder)와 중위순회(inorder) 정보를 활용해 실제 트리를 구하는 문제이다.
전위 순회는 root -> leftSubtree -> rightSubtree 순서로 방문한다.
중위 순회는 leftSubtree -> root -> rightSubtree 순서로 방문한다.
이를 그림으로 나타내면 다음과 같다.
preorder는 root가 가장 앞에 있는 것을 이용해서 inorder에서 root값을 가지는 순서를 찾는다.
inorder에서 root의 앞에 있는 노드들은 leftSubtree의 노드들로 그 개수(N)를 알 수 있다.
preorder에서 root 다음의 N개의 노드는 left Subtree에 해당하므로 각각의 leftSubtree와 rightSubtree를 분리해서 재귀로 함수를 호출하면 원본 트리를 구할 수 있다.
코드
이러한 방식은 노드를 한번씩만 방문하기 때문에 시간 복잡도는 O(n)이고 vector의 값을 깊은 복사로 진행시켰기 때문에 값을 복하지 않는 것이 훨씬 빠르다.
Map으로 inorder의 원소 위치를 저장시키고,
vector들을 copy시키고 넘겨서 진행하기 보다는 inorder의 범위 index를 넘겨서 빠르게 접근한다.
'알고리즘 공부 > LeetCode' 카테고리의 다른 글
| [LeetCode] 230. Kth Smallest Element in a BST (C++) (0) | 2023.07.06 |
|---|---|
| [LeetCode] 98. Validate Binary Search Tree (C++) (0) | 2023.07.05 |
| [LeetCode] 572. Subtree of Another Tree (C++) (0) | 2023.07.02 |
| [LeetCode] 297. Serialize and Deserialize Binary Tree (C++) (0) | 2023.03.05 |
| [LeetCode] 102. Binary Tree Level Order Traversal (C++) (0) | 2022.12.30 |