Python3刷题系列（九）

 # leetcode-230:二叉搜索树，中序遍历，beats 56.14%

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.cnt, self.val = 0, 0
        self.inOrder(root, k)
        return self.val
    
    def inOrder(self, root: TreeNode, k: int):
        if not root:
            return
        self.inOrder(root.left, k)
        self.cnt += 1
        if self.cnt == k:
            self.val = root.val
            return
        self.inOrder(root.right, k)

# leetcode-208： 字典树，前缀树，beats 39.87% 
class Node:
    def __init__(self):
        self.children = {}
        self.is_leaf = False

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = Node()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = Node()
            node = node.children[c]
        node.is_leaf = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_leaf

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

# leetcode-785：二分图：beats 80.75%
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        colors = [-1] * len(graph)
        for i in range(len(graph)):
            if colors[i] == -1 and not self.dfs(i, 0, colors, graph):
                return False
        return True
    
    def dfs(self, cur_node, cur_color, colors, graph):
        if colors[cur_node] != -1:
            return colors[cur_node] == cur_color
        
        colors[cur_node] = cur_color
        for next_node in graph[cur_node]:
            if not self.dfs(next_node, 1-cur_color, colors, graph):
                return False
        return True

# leetcode-144：二叉树前序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:  # 递归写法，beats 12.29%
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        if not root:
            return result
        result.append(root.val)
        result += self.preorderTraversal(root.left)
        result += self.preorderTraversal(root.right)
        return result


class Solution:  # 非递归写法，beats 84.21%
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        s = []
        if not root:
            return result
        s.append(root)
        while s:
            root = s.pop()
            result.append(root.val)
            if root.right:
                s.append(root.right)
            if root.left: 
                s.append(root.left) 
        return result

# leetcode-513：查找树的左下角值，beats  88.92%
class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
     q = [root]
      while q:
        root = q.pop(0)
        if root.right:
          q.append(root.right)
        if root.left:
          q.append(root.left)
      return root.val

# leetcode-684：并查集，beats  5.42%
class UnionFind:
    def __init__(self, n):
        self.ids = []
        for i in range(n+1):
            self.ids.append(i)
            
    def union(self, u, v):
        u_id = self.find(u)
        v_id = self.find(v)
        if u_id == v_id:
            return
        for i in range(len(self.ids)):
            if self.ids[i] == u_id:
                self.ids[i] = v_id
    
    def find(self, p):
        return self.ids[p]
    
    def connect(self, u, v):
        return self.find(u) == self.find(v)
                
    
class Solution:    
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        uf = UnionFind(len(edges))
        for e in edges:
            u, v = e[0], e[1]
            if uf.connect(u, v):
                return u, v
            uf.union(u, v)
        return -1, -1

# leetcode-207：拓扑排序，beats 90.89%
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graphic = [[] for i in range(numCourses)]
        for pre in prerequisites:
            graphic[pre[0]].append(pre[1])
        visited = [0]*numCourses
        for i in range(numCourses):
            if self.exist_cycle(visited, graphic, i):
                return False
        return True
    
    def exist_cycle(self, visited, graphic, cur_node):
        if visited[cur_node] == 1:
            return True
        if visited[cur_node] == 2:
            return False
        visited[cur_node] = 1
        for next_node in graphic[cur_node]:
            if self.exist_cycle(visited, graphic, next_node):
                return True
        visited[cur_node] = 2
        return False

# leetcode-110：平衡二叉树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:  # beats 19.84%
    def isBalanced(self, root: TreeNode) -> bool:
        if root is None:
            return True
        left_height = self.getHeight(root.left)
        right_height = self.getHeight(root.right)
        if abs(left_height - right_height) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)
    
    def getHeight(self, root: TreeNode) -> int:
        if root is None:
            return 0
        left_height = self.getHeight(root.left)
        right_height = self.getHeight(root.right)
        return max(left_height, right_height) +1


class Solution:  # 这个解决方案的逻辑错误点在哪？
    def _maxDepth(self, node: TreeNode) -> int:
        if (not node):
            return 0
        left_depth = self._maxDepth(node.left)
        right_depth = self._maxDepth(node.right)
        return max(left_depth, right_depth) + 1

    def _minDepth(self, node: TreeNode) -> int:
        if (not node):
            return 0
        left_depth = self._minDepth(node.left)
        right_depth = self._minDepth(node.right)
        return min(left_depth, right_depth) + 1
    
    def isBalanced(self, root: TreeNode) -> bool:
        return (self._maxDepth(root) - self._minDepth(root)) <= 1