leecode 4주차

트리:
귀속(110):https://leetcode.com/problems/balanced-binary-tree/description/
계층 이동(513):https://leetcode.com/problems/find-bottom-left-tree-value/description/

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        next_layer = [root]
        while next_layer:
            temp_next_layer = []
            layer_value = []
            for node in next_layer:
                if node.left:
                    temp_next_layer.append(node.left)
                if node.right:
                    temp_next_layer.append(node.right)
                layer_value.append(node.val)
                #print("layer_value:")
                #print(layer_value)
            next_layer = temp_next_layer
            #print("next_layer:")
            #print(next_layer)
        return layer_value[0]
        

앞뒤 순서(144):https://leetcode.com/problems/binary-tree-preorder-traversal/description/
반복 구현:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        return [root.val]+self.preorderTraversal(root.left)+self.preorderTraversal(root.right)

비귀속 실현:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        
        stack = [root]
        res = []
        while stack:
            cur = stack.pop()
            print(cur)
            print(stack)
            res.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
            
        return res
    

BST(230):https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.count = k
        self.res = 0
        def core(root):
            if root:
                #print(root)
                core(root.left)
                #print(self.count)
                self.count = self.count -1
                if self.count == 0:
                    self.res = root.val
                core(root.right)
        core(root)
        return self.res

Trie(208):https://leetcode.com/problems/implement-trie-prefix-tree/description/
https://blog.csdn.net/IOT_victor/article/details/88936762
 
그림:
이분도(785):https://leetcode.com/problems/is-graph-bipartite/description/
https://blog.csdn.net/weixin_37251044/article/details/88829810
토폴로지 정렬(207):https://leetcode.com/problems/course-schedule/description/
https://blog.csdn.net/IOT_victor/article/details/88936395
쿼리 세트(684):https://leetcode.com/problems/redundant-connection/description/
https://blog.csdn.net/qq_32424059/article/details/90207673------------저작권 성명: 본고는 CSDN 블로거'haimianjie 2012'의 오리지널 문장으로 CC4.0 BY-SA 저작권 협의에 따라 원문의 출처 링크와 본 성명을 동봉합니다.원문 링크:https://blog.csdn.net/haimianjie2012/article/details/93344894