数组

链表

二叉树

#94. 二叉树的中序遍历&节点个数
class TreeNode:
    def __init__(self,val = None,left = None,right = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    c = 0
    def inorder(self,root:TreeNode):
        l  = []
        def f(root):
            if root.left:f(root.left)
            self.c += 1
            l.append(root.val)
            if root.right:f(root.right)
        f(root)
        print(self.c)
        return l

if __name__ == '__main__':
    t = TreeNode(2)
    t0 = TreeNode(1,right=t)
    t1 = TreeNode(4)
    t2 = TreeNode(3,right = t1,left=t0)
    print(Solution().inorder(t2))

#99. 恢复二叉搜索树
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def recoverTree(self, root) -> None:
        """
        Do not return anything, modify root in-place instead.
        双指针 中序遍历二叉树，出现降序时记录第一个第二个降序点，结束交换
        """
        f = None
        s = None

        pre = TreeNode(float("-inf"))# 无穷小值
        p = root # p从根节点开始
        stack = [] #初始化栈
        while p or len(stack):# P为真或者栈不为空
            while p:# P为真
                stack.append(p)# p不空，则入栈
                p = p.left # 左子树遍历，整体来看实则是 拿中序遍历改的
            p = stack.pop()# 左子树到头了 开始出战
            if not f and pre.val > p.val:# f为空且pre的值大于p的值，将pre赋给f，即第一个异常点
                f = pre
            if f and pre.val > p.val:# f已经赋值，说明已经有异常点在之前出现，则当前是第二个异常点了。
                s = p
            pre = p
            p = p.right# 柚子树遍历
        f.val, s.val = s.val, f.val #遍历结束 交换错位值

#101.是否对称
def isSymmetric(self, root) -> bool:
    if not root: True

    def helper(left, right):
        if left is None and right is None:
            return True
        if left is not None and right is None:
            return False
        if left is None and right is not None:
            return False
        if left.val != right.val:
            return False
        else:
            return helper(left.left, right.right) and helper(left.right, right.left)

    return helper(root.left, root.right)

#104.DFS-树高&BFS
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def DFS(self, root):
        if not root:return 0
        l = self.DFS(root.left)
        r = self.DFS(root.right)
        return max(l, r) + 1
    
    def BFS(self,root):
        c = 0
        import queue
        if not root: return 0
        q = queue.Queue()
        q.put(root)
        while q.empty():
            for i in range(q.size()):
                node = q.get()  # 实现先进先出
                print(node.val)
                if node.lchild:
                    q.put(node.lchild)
                if node.rchild:
                    q.put(node.rchild)
            c += 1
        return c

#230. 二叉搜索树中第K小的元素
#Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    #中序遍历 存储res[],取出k-1个元素
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        if not root:return
        res = []
        def bst(root):
            if not root:return
            bst(root.left)
            res.append(root.val)
            bst(root.right)
        bst(root)
        return res[k-1]

if __name__ == '__main__':
    Solution().kthSmallest()

#235. 二叉搜索树的最近公共祖先
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if (root.val - p.val) * (root.val - q.val) <= 0:
            return root
        #否则，p和q位于root的同一侧，就继续往下找
        if root.val > p.val:
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return self.lowestCommonAncestor(root.right, p, q)

#236. 二叉树的最近公共祖先
#Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    ans = 0
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def dfs(root,p,q):
            if not root:return False
            lson = dfs(root.left, p, q)
            rson = dfs(root.right, p, q)
            if (lson and rson) or ((root.val == p.val or root.val == q.val) and (lson or rson)):
                self.ans = root
            return lson or rson or (root.val == p.val or root.val == q.val)
        dfs(root, p, q)
        return self.ans