(1)二叉树的遍历

1. 中序遍历
# -->走左边-->记录-->走右边
# 遍历BST非递减

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        return [i for i in inorder(root)]

#关于yield,next的使用

#找到BST中第k小的元素:
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        it =inorder(root)
        for i in range(k):
            ans=next(it)
        return ans
2.前序遍历
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def preorder(node):
            if node:
                yield node.val
                yield from preorder(node.left)
                yield from preorder(node.right)
        return [i for i in preorder(root)]
3. 后序遍历
# 3.1 N叉树后序遍历
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        def f(node):
            if node:
                for i in node.children: yield from f(i)
                yield node.val
        return [i for i in f(root)]
4. 层序遍历
# 4.1 DFS做法
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []

        def dfs(node, depth):
            if not node: return
            if len(ans) == depth:
                ans.append([node.val])
            else:
                ans[depth].append(node.val)
            dfs(node.left,depth+1)
            dfs(node.right,depth+1)

        dfs(root, 0)
        return ans

(2)112. 路径总和

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root: return False
        sum-=root.val
        if not root.left and not root.right :
            return sum==0
        return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)

(3)113.路径总和II

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。

class Solution:
    def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:
        if not root :return []
        stack=[([root.val],root)]
        ans=[]
        while stack:
            val,node=stack.pop()
            if not node.left and not node.right and sum(val)==sum_:
                ans.append(val)
            if node.left:
                stack.append((val+[node.left.val],node.left))
            if node.right:
                stack.append((val+[node.right.val],node.right))
        return ans

# 方法二:回溯法
class Solution:
    def pathSum(self, root: TreeNode, k: int) -> List[List[int]]:
        ans=[]
        def bk(node,path,k):
            if not node: return
            path.append(node.val)
            if k==node.val and not node.left and not node.right: 
                ans.append(path[:])
            bk(node.left,path,k-node.val)
            bk(node.right,path,k-node.val)
            path.pop()
        bk(root,[],k)
        return ans

(4)437.路径总和III

给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root: return 0
        return self.dfs(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)
    def dfs(self,root,path):
        if not root: return 0
        path-=root.val
        return (1 if path==0 else 0)+self.dfs(root.left,path)+self.dfs(root.right,path)

(5)翻转二叉树

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        def invert(root):
            if not root: return 
            root.left,root.right=root.right,root.left
            invert(root.left)
            invert(root.right)
        invert(root)
        return root

(6)二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        ans=[]
        def dfs(node,depth):
            if not node: return 
            if len(ans)==depth:
                ans.append([node.val])
            else:
                ans[depth].append(node.val)
            dfs(node.left,depth+1)
            dfs(node.right,depth+1)
        dfs(root,0)
        return [sum(i)/len(i) for i in ans]

(7)相同的树

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p==None and q==None: return True
        if p==None or q==None: return False
        if p.val!=q.val: return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right) 

(8)二叉树的深度

# 最大深度
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        else:
            left_height=self.maxDepth(root.left)
            right_height=self.maxDepth(root.right)
        return max(left_height,right_height)+1

# 最小深度
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        self.ans=float('inf')
        def dfs(node,depth):
            if depth>self.ans: return 
            if not node.left and not node.right:
                self.ans=min(self.ans,depth)
                return
            if node.left: dfs(node.left,depth+1)
            if node.right: dfs(node.right,depth+1)
        dfs(root,1)
        return self.ans

(9)左叶子之和

计算给定二叉树的所有左叶子之和。

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        self.ans=0

        def dfs(node):
            if not node: return 
            if node.left and node.left.val and (not node.left.left) and (not node.left.right):
                self.ans+=node.left.val
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return self.ans
        
#左叶子没有子节点

(10)二叉树的所有路径

给定一个二叉树,返回所有从根节点到叶子节点的路径。
["1->2->5", "1->3"]的类型表示

说明: 叶子节点是指没有子节点的节点。

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        ans=[]
        if not root: return ans
        def dfs(node,path):
            path+=str(node.val)
            if not node.left and not node.right: ans.append(path)
            if node.left: dfs(node.left,path+"->")
            if node.right: dfs(node.right,path+"->")
        dfs(root,"")
        return ans

(11)恢复二叉搜索树

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下,恢复这棵树。

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        nodes=[]      
        def dfs(root):    #中序遍历
            if not root: return 
            dfs(root.left)
            nodes.append(root)
            dfs(root.right)
        dfs(root)

        pre=nodes[0]
        x,y=None,None
        for i in range(1,len(nodes)):
            if pre.val > nodes[i].val:
                y=nodes[i]
                if not x: x=pre  # x为第一个出错的位置
            pre=nodes[i]   #准备下一次遍历
        if x and y: 
            x.val, y.val=y.val, x.val
#说明: 
# 空间复杂度O(n)
# 那个常数空间的莫里斯遍历不懂
# 在这种遍历情况下,二叉搜索树的值从小到大

(12)二叉树展开为链表

给定一个二叉树,原地将它展开为一个单链表。
If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        cur=root
        while cur:
            if cur.left:
                p=cur.left    #向左子树移动
                while p.right: p=p.right #找到root左子树的最右节点
                p.right=cur.right #将root右子树连到找到的节点
                cur.right=cur.left #再移回来
                cur.left=None
            cur=cur.right

(13)二叉搜索树中的众数

给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        ans=[]
        cnt,max_cnt,last=0,0,None
        for i in inorder(root):
            if i== last: cnt+=1
            else: cnt=1
            if cnt>max_cnt: ans=[i]
            elif cnt==max_cnt: ans.append(i)
            max_cnt=max(max_cnt,cnt)
            last=i
        return ans

# python O(1)的中序遍历

98. 验证二叉搜索树

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def inorder(node):
            if node: 
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        pre=float('-inf')
        for i in inorder(root):
            if i<=pre: return False
            pre=i
        return True 

101. 对称二叉树

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def check(n1, n2):
            if not n1 and not n2: return True
            elif not n1 or not n2: return False
            elif n1.val != n2.val:
                return False
            return check(n1.left,n2.right) and check(n1.right,n2.left)
        return check(root,root)

110. 平衡二叉树

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def dfs(node):
            if not node: return 0
            left = dfs(node.left)
            if left == -1:
                return -1
            right = dfs(node.right)
            if right == -1:
                return -1
            return 1 + max(left, right) if abs(left-right)<=1 else -1
        
        return dfs(root) != -1

208. 实现 Trie (前缀树)

Trie(发音类似 “try”)或者说 前缀树
是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。
这一数据结构有相当多的应用情景,例如自动补完和拼写检查。

1. 常规实现
class Trie:

    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

    def insert(self, word: str) -> None:
        cur = self
        for c in word:
            idx = ord(c) - ord('a')
            if not cur.children[idx]:
                cur.children[idx] = Trie()
            cur = cur.children[idx]
        cur.isEnd = True

    def search(self, word: str) -> bool:
        cur = self
        for c in word:
            idx = ord(c) - ord('a')
            if not cur.children[idx]:
                return False
            cur = cur.children[idx]
        if cur.isEnd:
            return True
        return False

    def startsWith(self, prefix: str) -> bool:
        cur = self
        for c in prefix:
            idx = ord(c) - ord('a')
            if not cur.children[idx]:
                return False
            cur = cur.children[idx]
        return True
2. 简易实现1
class Trie:

    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        p = self.root
        for c in word:
            if c not in p:
                p[c] = {}
            p = p[c]
        p['#'] = True

    def find(self, prefix):
        p = self.root
        for c in prefix:
            if c not in p:
                return None
            p = p[c]
        return p

    def search(self, word: str) -> bool:
        node = self.find(word)
        return node is not None and '#' in node

    def startsWith(self, prefix: str) -> bool:
        node = self.find(prefix)
        return node is not None
3. 简易实现2
class Trie:

    def __init__(self):
        self.children = defaultdict(Trie)
        self.is_word = False
        self.is_path = False

    def insert(self, word: str) -> None:
        cur = self
        for c in word:
            cur.is_path = True
            cur = cur.children[c]
        cur.is_word = True
        cur.is_path = True

    def search(self, word: str) -> bool:
        cur = self
        for c in word:
            cur = cur.children[c]
        return cur.is_word

    def startsWith(self, prefix: str) -> bool:
        cur = self
        for c in prefix:
            cur = cur.children[c]
        return cur.is_path

701. 二叉搜索树中的插入操作

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        p = root
        while p:
            if p.val<val:
                if p.right:
                    p = p.right
                else:
                    p.right = TreeNode(val)
                    break
            else:
                if p.left:
                    p = p.left
                else:
                    p.left = TreeNode(val)
                    break
        return root

230. 二叉搜索树中第K小的元素

使用 yield 和迭代器

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def preorder(node):
            if node:
                yield from preorder(node.left)
                yield node.val
                yield from preorder(node.right)
        
        it = preorder(root)
        for i in range(k):
            ans = next(it)
        return ans

235. 二叉搜索树的最近公共祖先

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'):
        if p.val<root.val and q.val<root.val:
            return self.lowestCommonAncestor(root.left,p,q)
        if p.val>root.val and q.val>root.val:
            return self.lowestCommonAncestor(root.right,p,q)
        return root

剑指 Offer 27. 二叉树的镜像

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return root
        left = self.mirrorTree(root.left)
        right = self.mirrorTree(root.right)
        root.left, root.right = right, left
        return root

剑指 Offer 37. 序列化二叉树

class Codec:
    def serialize(self, root):
        if not root: return "[]"
        q = collections.deque()
        q.append(root)
        res = []
        while q:
            node = q.popleft()
            if node:
                q.append(node.left)
                q.append(node.right)
                res.append(str(node.val))
            else: res.append("null")
        return "["+",".join(res)+"]"

    def deserialize(self, data):
        if data == "[]": return 
        vals, i = data[1:-1].split(','), 1
        root = TreeNode(int(vals[0]))
        q = collections.deque()
        q.append(root)
        while q:
            node = q.popleft()
            if vals[i] != "null":
                node.left = TreeNode(int(vals[i]))
                q.append(node.left)
            i+=1
            if vals[i] != "null":
                node.right = TreeNode(int(vals[i]))
                q.append(node.right)
            i+=1
        return root

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录