Binary Tree에서 최소공통조상 LCA를 찾는 로직.
직접 Tree와 스택을 종이에 써보면서 따라가보면 이해가 쉽다.
Leetcode 236. Lowest Common Ancestor of a Binary Tree
Input/Output
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root is None:
return None
# if p, q is root, return root
if p == root or q == root:
return root
# else look in left and right child
left_la = self.lowestCommonAncestor(root.left, p, q)
right_la = self.lowestCommonAncestor(root.right, p, q)
# either one of the chidren returned a node, meaning either p or q found on left or right branch.
# Example: assuming 'p' found in left child, right child returned 'None'. This means 'q' is
# somewhere below node where 'p' was found we dont need to search all the way,
# because in such scenarios, node where 'p' found is LCA
if left_la and not right_la:
return left_la
if right_la and not left_la:
return right_la
# if you found p, q from both left/right, that's the LCA.
# you can remove the if statement here as well
if left_la and right_la:
return root
응용 문제
반응형
'Software Engineering' 카테고리의 다른 글
리트코드 LeetCode 프리미엄 구독 후기 & 해지한 이유 (2) | 2023.12.02 |
---|---|
코딩테스트에 유용한 Python 코드조각들 (0) | 2023.01.02 |
[알고리즘] 이진 검색 binary search (0) | 2022.11.27 |
[알고리즘] 이진검색트리 BST(binary search tree) (0) | 2022.11.25 |
[알고리즘] 이진트리 binary tree DFS, BFS (0) | 2022.11.22 |