분류 전체보기351 [leetcode 98] Validate Binary Search Tree root 노드를 중심으로 왼쪽 subtree는 전부 root 노드보다 값이 작아야 하고 오른쪽 subtree는 전부 root 노드보다 값이 커야 한다. - subtree에 있는 모든 노드가 조건을 만족해야 한다. - 같아도 안된다. 1) inorder를 이용한 방식-stack 사용 - stack을 사용하여 왼쪽 가장 아래 노드까지 내려간다. - subtree기준으로 어쨌든 오른쪽 노드가 가장 크면 되기 때문에 값의 크기를 비교한 후엔 현재노드를 right 노드로 설정한다. using namespace std; class Solution { public: bool isValidBST(TreeNode* root) { stacks; long long inorder = -LONG_MAX; while(!s.emp.. 2020. 10. 4. [알고리즘] Tree Traversal - Depth First Traversal Depth First Traversal로 진행되는 트리 순회는 - preorder(root-> left -> right) - inorder(left->root->right) - postorder(left->right->root) 가 존재한다. www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/ Tree Traversals (Inorder, Preorder and Postorder) - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programmin.. 2020. 10. 4. [leetcode 94] Binary Tree Inorder Traversal Example 1: Input: root = [1,null,2,3] Output: [1,3,2] Example 2: Input: root = [] Output: [] Example 3: Input: root = [1] Output: [1] 1) recursive 풀이 class Solution { public: void Recursive(TreeNode* root, vector &answer){ if(root == nullptr){ return; } Recursive(root->left, answer); answer.push_back(root->val); Recursive(root->right, answer); } vector inorderTraversal(TreeNode* root) { vector a.. 2020. 10. 4. [백준 11725] 트리의 부모 찾기 www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 포인트 - 트리 정의하기 -> 인접리스트 사용: 벡터를 사용하기 - 트리 순회하기 -> bfs: 큐를 사용하여 모든 노드를 순회한다. - 주의: 매번 검색하면 시간 초과가 난다. 한번 순회하면서 부모노드를 모두 저장한다. #include #include #include #define MAX 100000 + 1 using namespace std; vector v[MAX]; int result[MAX]; int root = 1; void findParent() { queue .. 2020. 10. 4. 이전 1 ··· 78 79 80 81 82 83 84 ··· 88 다음
