Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://leetcode.com/problems/validate-binary-search-tree/description/
Validate Binary Search Tree - LeetCode
Can you solve this real interview question? Validate Binary Search Tree - Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: * The left subtree of a node contains only nodes with keys le
leetcode.com
풀이
난이도: Medium
다음과 같은 이진트리에서는 단순히 left가 value보다 작고 right가 value보다 큰지 확인하는 풀이는 오답이다.
노드 3이 5보단 작지만 4의 right side에 있다면 4보다 커야하기 때문이다.
따라서 이진트리를 삽입 순서대로 다시 분해하고 이진 트리의 규칙에 맞게 재조립하여 올바른 이진트리인지 확인하는 코드를 구현하였다.
1. vector<int> travelTreeBFS(TreeNode* root)
트리를 BFS로 순회하여 방문한 순서대로 vector에 삽입해 반환한다. (null 제외)
2. TreeNode* makeBST(vector<int> treeVal)
vector의 순서대로 노드를 삽입해 이진 트리를 만든다.
3. bool insertNodeToBST(TreeNode* root, int nodeVal)
트리의 root를 활용해 nodeVal인 node를 삽입한다.
4. bool checkBSTIsSame(TreeNode* targetRoot, TreeNode* BstRoot)
두가지 이진 트리가 같은지 비교한다.
하지만 성능은 좋지않다.
이번 풀이처럼 원시적인 풀이보다 조금더 생각해보면 빠르고 간단한 코드르 짤 수 있다.
위의 그림에서 3번 노드는 4보다 크고 5보다 작다는 범위만 만족하면 된다.
즉, 최소값과 최대값은 상위 노드에서 결정된다.
이를 활용하면 재귀함수로 각 노드를 한번씩만 방문해도 해결가능하다.
풀이 참조
Solution - Construct Binary Tree from Preorder and Inorder Traversal - LeetCode
View deleted_user's solution of Construct Binary Tree from Preorder and Inorder Traversal on LeetCode, the world's largest programming community.
leetcode.com
'알고리즘 공부 > LeetCode' 카테고리의 다른 글
| [LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree (C++) (0) | 2023.07.07 |
|---|---|
| [LeetCode] 230. Kth Smallest Element in a BST (C++) (0) | 2023.07.06 |
| [LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal (C++) (0) | 2023.07.04 |
| [LeetCode] 572. Subtree of Another Tree (C++) (0) | 2023.07.02 |
| [LeetCode] 297. Serialize and Deserialize Binary Tree (C++) (0) | 2023.03.05 |