Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://leetcode.com/problems/subtree-of-another-tree/description/
Subtree of Another Tree - LeetCode
Can you solve this real interview question? Subtree of Another Tree - Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a bin
leetcode.com
풀이
난이도: Easy
주어진 이진 subTree가 실제 이진 Tree내에 존재하는지 확인하는 문제.
일단 실제 Tree는 최대 2000개, subTree는 1000개의 노드를 가질 수 있으므로 브루트 포스로도 해결가능한 범위이다.
1. Tree의 root와 inputSubTree의 root가 일치하면 서로의 왼쪽과 오른쪽 subTree도 일치하는지 확인한다.
1-1. 중간에 일치하지 않는 노드가 확인되면 처음으로 돌아가서, Tree의 왼쪽과 오른쪽 subTree가 inputSubTree와 일치하는지 확인한다.
2. Tree의 root와 inputSubTree의 root가 일치하지 않으면 Tree의 왼쪽과 오른쪽 subTree가 inputSubTree와 일치하는지 확인한다.
모든 inputSubTree가 Tree의 특정 subTree와 일치해야 하므로, 1-1처럼 확인하던 중간에 불일치 노드가 발견되면 처음으로 돌아가서 왼쪽과 오른쪽 subTree에서부터 다시 일치 여부를 확인해야 한다.
이를 구현하기 위해 메인이되는 트리 순회함수 isSubtree()와 노드들의 일치여부를 확인하는 isSubtreeFromNotRoot()를 따로 구현하였다.
코드
'알고리즘 공부 > LeetCode' 카테고리의 다른 글
| [LeetCode] 98. Validate Binary Search Tree (C++) (0) | 2023.07.05 |
|---|---|
| [LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal (C++) (0) | 2023.07.04 |
| [LeetCode] 297. Serialize and Deserialize Binary Tree (C++) (0) | 2023.03.05 |
| [LeetCode] 102. Binary Tree Level Order Traversal (C++) (0) | 2022.12.30 |
| [LeetCode] 124. Binary Tree Maximum Path Sum (C++) (0) | 2022.12.28 |