반응형
- 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.
- 왼쪽 서브트리의 모든 노드는 해당 노드보다 작거나 같은 값을 가지며, 오른쪽 서브트리의 모든 노드는 해당 노드보다 큰 값을 가집니다.
- 2024-03-23 : First posting.
- 중위 순회는 왼쪽 서브트리를 먼저 탐색한 다음 현재 노드를 방문하고, 오른쪽 서브트리를 마지막으로 탐색하는 방법입니다.
- 중위 순회는 BST에서 노드들을 오름차순으로 방문하는 순서입니다.
- 전위 순회는 현재 노드를 먼저 방문한 다음 왼쪽 서브트리와 오른쪽 서브트리를 순차적으로 탐색하는 방법입니다.
- 후위 순회는 왼쪽 서브트리와 오른쪽 서브트리를 먼저 탐색한 다음 현재 노드를 방문하는 방법입니다.
root of a binary tree, return the inorder traversal of its nodes' values.
```[.linenums.lang-py]
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
res = []
stack = []
curr = root
while curr or stack:
while curr: # To the leftmost node.
stack.append(curr) # Stack and Pop
curr = curr.left
curr = stack.pop() # Stack and Pop
res.append(curr.val) # Append current node val.
curr = curr.right # To the right node.
return res
```/
```[.linenums.lang-py]
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
res = []
def inorder(root):
if not root:
return
inorder(root.left)
res.append(root.val)
inorder(root.right)
inorder(root)
return res
```/
```[.linenums.lang-ts]
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function inorderTraversal(root: TreeNode | null): number[] {
let res = []
let inorder = function (root: TreeNode | null) {
if (!root) {
return
}
inorder(root.left);
res.push(root.val);
inorder(root.right);
};
inorder(root)
return res
};
```/
### 95. Unique Binary Search Trees II
출처: leetcode.com :: 95. Unique Binary Search Trees II
Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.
```[.linenums.lang-py]
memos = defaultdict(list)
def helper(left, right): # construct trees using left->right numbers
if left > right:
return [None]
if (left, right) in memos:
return memos[(left, right)]
for i in range(left, right+1): # i can choose right, so the range is to right+1
lefts = helper(left, i-1)
rights = helper(i+1, right)
for l in lefts: # go through all the lefts and rights
for r in rights:
root = TreeNode(i, l, r) # root created
memos[(left, right)].append(root)
return memos[(left, right)] # just return the stored values
helper(1, 8)
class Solution:
def generateTrees(self, n: int) -> list[Optional[TreeNode]]:
return helper(1, n)
```/
```[.linenums.lang-py]
from typing import Optional
from functools import lru_cache
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val: int=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __repr__(self):
return f"TreeNode{{val: {self.val}, left: {self.left}, right: {self.right}}}"
class Solution:
def generateTrees(self, n: int) -> list[Optional[TreeNode]]:
@lru_cache
def buildtree(left, right):
if right < left:
return [None]
trees = []
for nd in range(left, right + 1):
ltrees = buildtree(left, nd - 1)
rtrees = buildtree(nd + 1, right)
for ltree in ltrees:
for rtree in rtrees:
root = TreeNode(nd, ltree, rtree)
trees.append(root)
return trees
return buildtree(1, n)
sol = Solution()
lis = sol.generateTrees(8)
for li in lis:
print(f"{li = }")
```/
### 96. Unique Binary Search Trees
출처: leetcode.com :: 96. Unique Binary Search Trees
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
```[.linenums.lang-py]
memo = {0:1, 1:1}
class Solution:
def numTrees(self, n: int) -> int:
if n<=1:
return 1
res = 0
if n in memo:
return memo[n]
for i in range(n):
res += self.numTrees(i) * self.numTrees(n-1-i)
memo[n] = res
return res
```/
```[.linenums.lang-py]
class Solution:
@lru_cache
def numTrees(self, n: int) -> int:
if n<=1:
return 1
res = 0
for i in range(n):
res += self.numTrees(i) * self.numTrees(n-1-i)
return res
```/
### 98. Validate Binary Search Tree
출처: leetcode.com :: 98. 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
of a node contains only nodes with keys less than the node's key. - The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
subtree: A subtree of
```[.linenums.lang-py]
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValidHelper(root: Optional[TreeNode], min_: int, max_: int) -> bool:
if not root:
return True
return min_<root.val<max_ and isValidHelper(root.left, min_, root.val) and isValidHelper(root.right, root.val, max_)
return isValidHelper(root, -math.inf, math.inf)
```/
### 99. Recover Binary Search Tree
출처: leetcode.com :: 99. Recover Binary Search Tree
You are given the treeName is a tree consisting of a node in treeName and all of its descendants.
root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
```[.linenums.lang-py]
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def inorderBST(root):
if root:
inorderBST(root.left)
if self.prev.val > root.val:
if not self.first:
self.first = self.prev
self.second = root
self.prev = root
inorderBST(root.right)
self.prev = TreeNode(-math.inf)
self.first = self.second = None
inorderBST(root)
self.first.val, self.second.val = self.second.val, self.first.val
```/
### 100. Same Tree
출처: leetcode.com :: 100. Same Tree
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
```[.linenums.lang-py]
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p == None and q == None:
return True
if p and q:
return p.val==q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return False
```/
### 101. Symmetric Tree
출처: leetcode.com :: 101. Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
```[.linenums.lang-py]
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def isSym(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
if not left and not right:
return True
if left and right:
return left.val==right.val and isSym(left.left, right.right) and isSym(left.right, right.left)
return False
return isSym(root.left, root.right)
```/
### 102. Binary Tree Level Order Traversal
출처: leetcode.com :: 102. Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
```[.linenums.lang-py]
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res = [[root.val]]
nodesRes = [[root]]
def addLevel(levelRoots: List[TreeNode]) -> Optional[List[TreeNode]]:
nodeValues = []
nodes = []
for levelRoot in levelRoots:
if levelRoot.left:
nodes.append(levelRoot.left)
nodeValues.append(levelRoot.left.val)
if levelRoot.right:
nodes.append(levelRoot.right)
nodeValues.append(levelRoot.right.val)
if len(nodeValues) > 0:
res.append(nodeValues)
nodesRes.append(nodes)
return True
return False
while addLevel(nodesRes[-1]):
pass
return res
```/
### 105. Construct Binary Tree from Preorder and Inorder Traversal
출처: leetcode.com :: 105. Construct Binary Tree from Preorder and Inorder Traversal
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.
```[.linenums.lang-py]
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
# Create a hashmap to store the indices of elements in the inorder list
inorder_map = {val: index for index, val in enumerate(inorder)}
# Define a recursive function to build the binary tree
def build(pre_start: int, pre_end: int, in_start: int, in_end: int) -> Optional[TreeNode]:
# Base case: If the start index in the preorder list is greater than the end index,
# it indicates that the current subtree is null, so return None
if pre_start > pre_end:
return None
# Extract the value of the root node from the preorder list using the start index
root_val = preorder[pre_start]
root = TreeNode(root_val)
# Find the index of the root node's value in the inorder list using the hashmap
in_index = inorder_map[root_val]
# Determine the size of the left subtree
left_size = in_index - in_start
# Recursively build the left subtree
root.left = build(pre_start + 1, pre_start + left_size, in_start, in_index - 1)
# Recursively build the right subtree
root.right = build(pre_start + left_size + 1, pre_end, in_index + 1, in_end)
return root
# Call the build function with initial parameters corresponding to the entire preorder and inorder lists
return build(0, len(preorder) - 1, 0, len(inorder) - 1)
```/
```[.linenums.lang-py]
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
inorder_map = { v:i for i,v in enumerate(inorder) } # v -> inorder index
curr_node_preorder_index = 0
def buildTree(left: int, right: int) -> Optional[TreeNode]:
if left > right:
return None
nonlocal curr_node_preorder_index
curr_node_value = preorder[curr_node_preorder_index]
curr_node_inorder_index = inorder_map[curr_node_value]
curr_node = TreeNode(curr_node_value)
curr_node_preorder_index += 1
curr_node.left = buildTree(left, curr_node_inorder_index-1) # left first (preorder)
curr_node.right = buildTree(curr_node_inorder_index+1, right)
return curr_node
return buildTree(0, len(inorder)-1)
```/
### 106. Construct Binary Tree from Inorder and Postorder Traversal
출처: leetcode.com :: 106. Construct Binary Tree from Inorder and Postorder Traversal
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
```[.linenums.lang-py]
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
inorder_index = { val:i for i,val in enumerate(inorder)}
def helper(l,r):
if l>r:
return None
root = TreeNode(postorder.pop())
index = inorder_index[root.val]
root.right = helper(index+1,r) # right first (postorder)
root.left = helper(l,index-1)
return root
return helper(0, len(inorder)-1)
```/
### 107. Binary Tree Level Order Traversal II
출처: leetcode.com :: 107. Binary Tree Level Order Traversal II
Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).
```[.linenums.lang-py]
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
values = [[root.val]]
nodes = [[root]]
def addLevel(levelNodes: List[TreeNode]) -> bool:
nextValues = []
nextNodes = []
for levelNode in levelNodes:
if levelNode.left:
nextValues.append(levelNode.left.val)
nextNodes.append(levelNode.left)
if levelNode.right:
nextValues.append(levelNode.right.val)
nextNodes.append(levelNode.right)
if len(nextNodes) > 0:
values.append(nextValues)
nodes.append(nextNodes)
return True
else:
return False
while addLevel(nodes[-1]):
pass
return values[::-1]
```/
### 108. Convert Sorted Array to Binary Search Tree
출처: leetcode.com :: 108. Convert Sorted Array to Binary Search Tree
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
```[.linenums.lang-py]
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def helper(left: int, right: int) -> Optional[TreeNode]:
if left > right:
return None
elif left == right:
return TreeNode(nums[left])
# elif left+1 == right:
# return TreeNode(nums[right], TreeNode(nums[left]))
mid = (left + right) // 2 # 1 ~ 7: 8//2 = 4
root = TreeNode(nums[mid], helper(left, mid-1), helper(mid+1, right))
return root
return helper(0, len(nums)-1)
```/
### 109. Convert Sorted List to Binary Search Tree
출처: leetcode.com :: 109. Convert Sorted List to Binary Search Tree
Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree.
```[.linenums.lang-py]
class Solution:
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
if not head:
return None
nums = [head.val]
while head.next != None:
head = head.next
nums.append(head.val)
def helper(left: int, right: int) -> Optional[TreeNode]:
if left > right:
return None
elif left == right:
return TreeNode(nums[left])
mid = (left + right) // 2
return TreeNode(nums[mid], helper(left, mid-1), helper(mid+1, right))
return helper(0, len(nums)-1)
```/
```[.linenums.lang-py]
class Solution:
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
def getMid(head):
prev, slow, fast = None, head, head
while fast and fast.next:
prev, slow, fast = slow, slow.next, fast.next.next
if prev:
prev.next = None
return slow
if head == None:
return None
elif head.next == None:
return TreeNode(head.val)
mid = getMid(head)
root = TreeNode(mid.val, self.sortedListToBST(head), self.sortedListToBST(mid.next))
return root
```/
### 110. Balanced Binary Tree
출처: leetcode.com :: 110. Balanced Binary Tree
Given a binary tree, determine if it is
height-balanced: 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.
```[.linenums.lang-py]
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def inorder(root: TreeNode, level: int, maxLevel: int) -> (int, bool):
if not root:
return maxLevel, True
leftMax, leftBal = inorder(root.left, level+1, level)
rightMax, rightBal = inorder(root.right, level+1, level)
return max(leftMax, rightMax), leftBal and rightBal and abs(leftMax - rightMax) <= 1
return inorder(root, 1, 1)[1]
```/
### 113. Path Sum II
출처: leetcode.com :: 113. Path Sum II
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
```[.linenums.lang-py]
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return []
res = []
path = []
def search(cur, sumUntil):
path.append(cur.val)
if not cur.left and not cur.right and sumUntil == targetSum:
res.append(path[:]) # shallow copy of path
if cur.left:
search(cur.left, sumUntil+cur.left.val)
if cur.right:
search(cur.right, sumUntil+cur.right.val)
path.pop()
search(root, root.val)
return res
```/
### 114. Flatten Binary Tree to Linked List
출처: leetcode.com :: 114. Flatten Binary Tree to Linked List
Given the root of a binary tree, flatten the tree into a "linked list":
- The "linked list" should use the same
TreeNodeclass where therightchild pointer points to the next node in the list and theleftchild pointer is alwaysnull. - The "linked list" should be in the same order as a pre-order traversal of the binary tree.
반응형