이진 탐색 트리6 [LEET CODE] 105. Construct Binary Tree from Preorder and Inorder Traversal # Problem Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. Constraints: 1 2021. 5. 24. [LEET CODE] 783. Minimum Distance Between BST Nodes # Problem Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree. Constraints: The number of nodes in the tree is in the range [2, 100]. 0 int: if root.left: self.minDiffInBST(root.left) self.result = min(self.result, root.val - self.prev) self.prev = root.val if root.right: self.minDiffInBST(root.right) return self.r.. 2021. 5. 24. [LEET CODE] 1038. Binary Search Tree to Greater Sum Tree # Problem Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. As a reminder, a binary search tree is a tree that satisfies these constraints: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of.. 2021. 5. 24. [LEET CODE] 108. Convert Sorted Array to Binary Search Tree # Problem Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one. Constraints: 1 2021. 5. 19. [코딩 + 알고리즘 완주반] 15일차. 힙 # 힙 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 # 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용 # 힙 구조 힙은 최대값을 구하기 위한 구조(최대힙) 와, 최소값을 구하기 위한 구조( 최소 힙) 으로 분류 가능 1. 각 노드의 값은 해당 노드의 자식노드가 가진 값보다 크거나 같다(최대힙) 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같음 2. 완전 이진 트리 .. 2021. 3. 29. [코딩 + 알고리즘 완주반] 14일차. 트리 # 트리 구조 트리 : Node 와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조 이진트리형태의 구조로 탐색 알고리즘 구현을 위해 많이 사용 # 알아둘 용어 Node : 트리에서 데이터를 저장하는 기본 요소( 데이터와 다른 연결된 노드에 대한 branch 정보 포함) Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 level 0으로 하였을 때, 하위 branch로 연결된 노드의 깊이 Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 Child Node : 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node(Terminal Node) : Child Node가 하나도 없는 노드 Silbinng(Brother node) : 동일한 Parent No.. 2021. 3. 28. 이전 1 다음 반응형
