본문 바로가기

알고리즘 문제풀이291

[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.
[leetcode 102] Binary Tree Level Order Traversal 같은 레벨의 노드끼리 배열을 만들어 return한다. Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], return its level order traversal as: [ [3], [9,20], [15,7] ] 풀이 - 큐와 bfs를 이용하여 레벨 별로 노드를 저장한다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNod.. 2020. 10. 3.
[leetcode 993] Cousins in Binary Tree - 두 노드가 부모가 다르고 같은 depth를 가진 cousin인지 확인하기 In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1. Two nodes of a binary tree are cousins if they have the same depth, but have different parents. We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree. Return true if and only if the nodes corre.. 2020. 10. 3.

티스토리툴바