목록bst (2)

궁금한게 많은 개발자 노트

[ leetcode ] 450. Delete Node in a BST

Binary Search Tree가 주어졌을 때, 한 노드를 제거하고 재배치한 BST를 반환하는 문제입니다. 여러 경우의 수가 있지만, 우선 한 노드를 삭제할 때 기본적인 규칙은 다음과 같습니다. 삭제할 노드의 자식 중 한쪽 노드만 존재하는 경우, 삭제할 노드 위치를 해당 노드로 변경 삭제할 노드의 자식 둘 다 존재하는 경우, 왼쪽 자식 노드를 삭제할 노드로 대체한다고 하면 왼쪽 자식 노드의 오른쪽 노드를 삭제할 노드의 오른쪽 자식의 가장 왼쪽 자식에 추가해주는 로직이 필요 (반대의 경우도 가능) 아래 링크를 참고하면 이해에 도움이 될 것 같습니다. https://leetcode.com/problems/delete-node-in-a-bst/solutions/1591176/c-simple-solution-..
Algorithm 2023. 5. 2. 13:33
[ leetcode ] 235. Lowest Common Ancestor of a Binary Search Tree

Binary Search Tree가 주어졌을 때, 서로 다른 두 노드의 가장 낮은 level의 공통 조상을 찾는 문제입니다. (Lowest Common Ancestor) BST의 특성을 잘 이해하여 한 노드의 값보다 크면 오른쪽 자식, 작으면 왼쪽 자식에 존재한다는 개념을 이용합니다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* ..
Algorithm 2023. 5. 2. 10:46
Prev 1 Next