数据结构-树

宅蓝三木

发布于 2024-10-09 21:13:28

880

发布于 2024-10-09 21:13:28

文章被收录于专栏：三木的博客

二叉树的遍历

按照根节点的访问顺序分为前序、中序和后序遍历
遍历二叉树的时间复杂度为O(n)，空间复杂度为O(h)

二叉树剪枝：https://leetcode.cn/problems/pOCWxh/

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

序列化与反序列化二叉树:

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

二叉搜索树

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

寻找二叉搜索树中的目标节点

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

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]

二叉搜索树中两个节点之和：

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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-09-15，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历