树

(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的使用

二叉搜索树的中序遍历是有序的。

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

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

# 使用 yield 和迭代器

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. 后序遍历

# 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. 层序遍历

# 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)

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

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)

(3)LCA 问题

LCA（Lowest Common Ancestor），最近公共祖先

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

利用 BST 的性质

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        node = root
        while True:
            if node.val > p.val and node.val > q.val:
                node = node.left
            elif node.val < p.val and node.val < q.val:
                node = node.right
            else:
                break
        return node

236. 二叉树的最近公共祖先⭐

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left: return right
        if not right: return left
        return root    

5944. 从二叉树一个节点到另一个节点

刚开始只找一个值

class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        def vis(node = root, father = None):
            if not node:
                return 
            if node.val == startValue:
                self.start = node
            node.father = father
            vis(node.left, node)
            vis(node.right, node)
        vis()

        visited = set([startValue])
        to_vis = [[self.start, ""]]
        while to_vis:
            node, path = to_vis.pop(0)
            if node.val == destValue:
                return path
            if node.father and node.father.val not in visited:
                visited.add(node.father.val)
                to_vis.append([node.father, path+"U"])
            if node.left and node.left.val not in visited:
                visited.add(node.left.val)
                to_vis.append([node.left, path+"L"])
            if node.right and node.right.val not in visited:
                visited.add(node.right.val)
                to_vis.append([node.right, path+"R"])
        return None

(4)BST 问题

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 

501. 二叉搜索树中的众数

给定一个有相同值的二叉搜索树（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)的中序遍历

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

其它问题

翻转二叉树

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

二叉树的层平均值

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

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]

相同的树

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

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

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) 

二叉树的深度

# 最大深度
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

左叶子之和

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

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
        
#左叶子没有子节点

二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。
用["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

恢复二叉搜索树

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

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

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)
# 那个常数空间的莫里斯遍历不懂
# 在这种遍历情况下，二叉搜索树的值从小到大

二叉树展开为链表

给定一个二叉树，原地将它展开为一个单链表。
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

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

剑指 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