복's
[ LeetCode - 100 ] Same Tree 본문
https://leetcode.com/problems/same-tree/description/
Same Tree - LeetCode
Can you solve this real interview question? Same Tree - Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the
leetcode.com
주어진 트리가 동일한 트리인지 비교하는 문제로 나는 트리를 순회하면서 매번 트리의 노드가 갖는 value의 값이 같은지 확인하였다.
오늘은 다른 사람들의 코드는 분석하지는 않았다. (숏 코드)
물론 눈으로는 봤는데 바쁜 기간이라서라는 핑계와 함께
[ 📌 풀이 ]
1) root 노드부터 순회하는 코드를 만든다.
2) 노드가 갖는 val의 값이 같은지 비교한다. (같은 트리인지 비교하기 위해서)
3 - 1) 트리의 순회가 중간에 끝나면 같은 트리가 아니다.
3 - 2) 트리의 순회가 완전히 끝나면 같은 트리다.
다른 풀이로 기발한 풀이와 별개로 python에서 str로 캐스팅하여 문자열로 비교해서 푸는 풀이도 봤다. (나름 기발한듯? 편법이지만 사실 어떻게 푸는지 정해진건 아니니까 기발하다고 하는게 나는 맞는거 같다.)
[ 📌 코드 - Python ]
"""
# Author : Lee In Bok
# Date : 2023.11.14(Tue)
# Spend Time: 17m 32s
# Runtime : 34 ms (Beats 81.70%)
# Memory : 16.4 MB (Beats 20.68%)
# Algoritm : Tree
"""
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
self.ans = True
def order(p, q):
if not self.ans:
return
if p or q:
try :
if p.val != q.val:
self.ans = False
return
if p.left or q.left:
order(p.left, q.left)
if p.right or q.right:
order(p.right, q.right)
except:
self.ans = False
order(p, q)
return self.ans[ 📌 코드 - Java ]
/**
* Author : Lee In Bok
* Date : 2023.11.14(Tue)
* Spend Time: 17m 32s
* Runtime : 0 ms (Beats 100%)
* Memory : 40.4 MB (Beats 06.28%)
* Algoritm : Tree
*/
class Solution {
public boolean ans = true;
public boolean isSameTree(TreeNode p, TreeNode q) {
order(p, q);
return ans;
}
public void order(TreeNode p, TreeNode q){
if(!ans) return;
if(p != null || q != null){
try {
if(p.val != q.val){
ans = false;
return;
}
if(p.left != null || q.left != null) order(p.left, q.left);
if(p.right != null || q.right != null) order(p.right, q.right);
} catch(Exception e){
ans = false;
}
}
}
}[ 📌 결과 - Python ]
[ 📌 결과 - Java ]
'알고리즘 > LeetCode' 카테고리의 다른 글
| [ LeetCode - 178 ] Rank Scores (2) | 2023.11.20 |
|---|---|
| [ LeetCode - 176 ] Second Highest Salary (1) | 2023.11.18 |
| [ LeetCode - 181 ] Employees Earning More Than Their Managers (0) | 2023.11.12 |
| [ LeetCode - 94 ] Binary Tree Inorder Traversal (0) | 2023.11.12 |
| [ LeetCode - 175 ] Combine Two Tables (0) | 2023.11.11 |
