(Leetcode) 235 - Lowest Common Ancestor of a Binary Search Tree
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
내가 작성한 풀이
이 문제에서는 LCA 에 대한 개념이 있어야 한다.
LCA가 되는 케이스를 2가지로 생각하였다. 하나는 노드의 양쪽에 나눠져 있는 경우, 다른 하나는 하나의 노드 아래 포함되어 있는 경우이다.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return dfs(root, p, q);
}
private TreeNode dfs(TreeNode node, TreeNode p, TreeNode q) {
if (node == null) {
return null;
}
TreeNode left = dfs(node.left, p, q);
TreeNode right = dfs(node.right, p, q);
if ((left != null && right != null) || node.val == p.val || node.val == q.val) {
return node;
}
return left != null ? left : right;
}
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다. 트리가 균등할 경우 O(logn)에 가까워진다.