二叉树的遍历

  • 按照根节点的访问顺序分为前序、中序和后序遍历
  • 遍历二叉树的时间复杂度为O(n)，空间复杂度为O(h)
  1. 二叉树剪枝：https://leetcode.cn/problems/pOCWxh/
1
2
3
4
5
6
7
8
9
10
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        if root.left is None and root.right is None and root.val == 0:
            return None
        else:
            return root
  1. 序列化与反序列化二叉树: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def dfs(s, idx):
    if not s:
        return None
    if idx[0] >= len(s):
        return None
    if s[idx[0]] == "#":
        idx[0] += 1
        return None
    node = TreeNode(s[idx[0]])
    idx[0] += 1
    node.left = dfs(s, idx)
    node.right = dfs(s, idx)
    return node

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        if root is None:
            return "#"
        c = str(root.val)
        lc = self.serialize(root.left)
        rc = self.serialize(root.right)
        return f'{c},{lc},{rc}'
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        s = data.split(',')
        return dfs(s, [0])

二叉搜索树

  • 它是一棵二叉树，其中每个节点都满足以下性质：左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。
  • 对于任意节点，其左右子树也都是都是二叉搜索树。
  1. 寻找二叉搜索树中的目标节点

Link: https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def dfs(node, heap, cnt):
    if node is None:
        return
    dfs(node.right, heap, cnt)
    heap.append(node.val)
    if len(heap) == cnt:
        return
    dfs(node.left, heap, cnt)

class Solution:
    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:
        heap = []
        dfs(root, heap, cnt)
        return heap[cnt - 1]
  1. 二叉搜索树中两个节点之和：

Link: https://leetcode.cn/problems/opLdQZ/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        def dfs(node, m, k):
            if node is None:
                return
            if k - node.val in m:
                self.res = True
                return
            m[node.val] = True
            dfs(node.left, m, k)
            dfs(node.right, m, k)
        m = {}
        self.res = False
        dfs(root, m, k)
        return self.res