Bran Zhang
Go back

算法笔记——树

Updated:

简介

感觉树相关的算法问题离不开树的构建和搜索，不同类型的树有不同的搜索姿势，遍历也算是一种搜索吧，从头到尾，无目的的那种。

构建是为了组织好数据，方便搜索。涉及到的问题一般是添，删，改，查。

搜索则像是在解决实际的问题，既有通用的搜索方式，特殊形态的树也存在着特有的搜索方式。

常见应用场景

不同类型的树

二叉搜索树

二叉搜索树是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：

BST 示例

上面3题中，第一题是BST的插入问题，后两题是BST的搜索问题。

插入的算法可以用递归来完成，这里的插入还算简单，不需要对树的其他节点做调整，参考代码：

def insertIntoBST(self, root, val):
    if root.val > val:
        if not root.left:
            root.left = TreeNode(val)
        else:
            self.insertIntoBST(root.left, val)
    else:
        if not root.right:
            root.right = TreeNode(val)
        else:
            self.insertIntoBST(root.right, val)
    return root

二叉搜索树的范围和，也就是需要找出所有在二叉树中指定区间范围内的值。可以使用深度遍历或者广度遍历。下面的是广度遍历的参考代码：

def rangeSumBST(self, root, L, R):
    ans = 0
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            if L <= node.val <= R:
                ans += node.val
            if L < node.val:
                stack.append(node.left)
            if node.val < R:
                stack.append(node.right)
    return ans

对于寻找二叉搜索树中第K小的元素，需要用到中序遍历，将在下面提到。

红黑树

红黑树本质上是一棵二叉搜索树，但它在二叉搜索树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为 O(logn)O(logn) 。

红黑树的特性：

红黑树的图例

红黑树的左右旋是比较重要的操作，左右旋的目的是调整红黑节点结构，转移黑色节点位置，使其在进行插入、删除后仍能保持红黑树的 5 条性质。

红黑树的左右旋

红黑树的增删操作比较复杂，在此就不多说了。看下面这个问题。

**区间和的个数：**Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive. 链接

在考虑这条题目之前，先来看看“计算右侧小于当前元素的个数”这个题目。给定一个数组，统计每个数的右侧，有多少个小于当前数值的元素。接解题的思路是，从右往左遍历，在遍历的同时，构建一颗二叉搜索树。每当需要在二叉搜索树中插入元素时，就可以顺便统计一下有多少节点小于当前值，也就是在数组中当前元素的右侧有多少个数小于当前值。

回到这条题目：在给定数组中，求区间和满足指定范围的的区间的个数。可以简单的双重循环一遍，但是这样效率很差。结合“”题目来看，事先计算好数组的求和结果可以提高一些效率，定义新的数组 T，令 Ti=Ti =。题目中想要求的区间实际上就是，区间 (i,j)(i,j) 的和等于 。

问题就转换为了：对于每一个位置，在它的右侧有多少个元素满足“与当前位置的差在指定的区间范围内”。所以，解法参照上面的题目，从右往左遍历，一边遍历一边构造二叉树，从而解决题目中的问题。考虑到输入的数组的大小，红黑树可能比二叉搜索树更加合适。

霍夫曼树

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。 霍夫曼 编码是哈夫曼树的一个应用，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现几率的方法得到的，出现几率高的字母使用较短的编码，反之出现几率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

霍夫曼树的构建过程可参考此文章。LeetCode上关于霍夫曼树的问题不多，下面是我找到的其中一条：

**建造街区的最短时间：**You are given a list of blocks, where blocks[i] = t means that the i-th block needs t units of time to be built. A block can only be built by exactly one worker. A worker can either split into two workers (number of workers increases by one) or build a block then go home. Both decisions cost some time. The time cost of spliting one worker into two workers is given as an integer split. Note that if two workers split at the same time, they split in parallel so the cost would be split. Output the minimum time needed to build all blocks. 链接

这个问题和霍夫曼树有什么关联呢？如果一个街区需要更多的时间来建造，也就对应着出现几率高的字母，得到的编码就越短，在工期的安排上就越优先。在建造工期长的街区的同时，另一个工人可以把时间花在招工，并完成工期短的街区。具体的构建过程，以输入参数 blocks [1, 2, 4, 7, 10]，split cost 3 为例：

对街区工期进行排序，先分析前两个：

对于前两个街区，需要花费的时间是，先花3天时间招个工，2个工人分别建造街区，时间花费max(1,2)天，共计split+max(1,2)，也就是5天。其余的依此类推。

最终，一个霍夫曼树就算构建完成了，生成的过程是自底向上的，实际的执行过程是自顶向下的，也就是：第一个工人先花3天招一个新工人，让他去建造需要花10天的街区；同时，第一个工人再花3天招一个新工人，让他去建造需要花7天的街区；依此类推。直到最后一个需要花1天的街区，就自己上了。

剩下的就代码实现了，参考代码：

def minBuildTime(self, blocks, split):
    heapq.heapify(blocks)
    while True:
        if len(blocks) == 1:
            return blocks[0]
        a, b = heapq.heappop(blocks), heapq.heappop(blocks)
        # as b is great or eqaul to a, so no need to max(a,b) + split
        heapq.heappush(blocks, b+split)

树的搜索及遍历

广度优先遍历和深度优先遍历

广度优先遍历

从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。

当问题的解对应着一颗树的层数，或者需要在同层的节点中寻找答案的时候，广度优先遍历可能是一个不错的选择。

上面的问题中，前2个问题是以树的每一层为单位进行的，第1题需要输出树的每一层，并根据行数进行反转。第2题需要判断树的每一层是否是对称。第3个问题需要广度优先遍历这棵树，直到出现空节点。

二叉树的最小深度的广度优先遍历的参考代码：

def minDepth(self, root):
    if not root:
        return 0
    
    node_list = [root]
    depth = 1
    
    while node_list:
        temp = []
        for node in node_list:
            if not node.left and not node.right:
                return depth
            if node.left:
                temp.append(node.left)
            if node.right:
                temp.append(node.right)
        depth += 1
        node_list = temp

当然，递归也是一个不错的选择：

def minDepth(self, root: TreeNode) -> int:
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    if not root.left:
        return 1 + self.minDepth(root.right)
    if not root.right:
        return 1 + self.minDepth(root.left)
    return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

深度优先遍历

沿着树的子节点遍历树，尽可能深的搜索树的分支。当节点v的所有子节点都己被探寻过，搜索将回溯到节点v的父节点。这一过程一直进行到已发现所有节点为止。

相比广度优先遍历，深度优先遍历能够很方便的获取一条路径上的前后节点，因此适用性更广一些。深度优先遍历常常以递归的形式来实现。

第一题路径之和需要判断一条从根节点到叶子节点的路径之和是否等于给定值。如果使用广度优先遍历就需要在遍历过程中将整颗树的路径都保存下来，会占用很大的空间。第二题需要寻找2个子节点的最近公共祖先。采用递归，判断当前节点的左右子树是否包含给定的节点，如果左子树包含且右子树也包含，则当前节点为最近公共祖先。参考代码：

def lowestCommonAncestor(self, root, p, q):
    if not root: return None
    if p == root or q == root:
        return root
    left = self.lowestCommonAncestor(root.left, p , q)
    right = self.lowestCommonAncestor(root.right, p , q)
        
    if left and right:
        return root
    if not left:
        return right
    if not right:
        return left

两者比较

广度优先遍历一般需要存储产生的所有结点，占的存储空间要比深度优先遍历大得多，因此程序设计中，必须考虑溢出和节省内存空间得问题。

感觉没有什么问题是只能用广度优先遍历或者深度优先遍历来解，无非是一种更方便一点，另外一种在编码难度和效率上略逊一点。

上面的题目既可以用广度优先遍历来实现，也可以用深度优先遍历来实现。

第一题N叉树的最大深度可以使用广度优先遍历，统计总共遍历了几层。也可以使用深度优先遍历，计算各个从根节点到叶子节点的路径的长度，取最大值。

第二题使用两种遍历方法的解题思路与第一题类似。

第三题删除无效括号，因为可能存在多组解，所以需要将所有的结果输出。用深度优先遍历或者广度优先遍历均可。下面分别是通过不同的遍历方法来求解：

def removeInvalidParentheses(self, s):
    def dfs(s):
        mi = calc(s)
        if mi == 0:
            return [s]
        ans = []
        for x in range(len(s)):
            if s[x] in ('(', ')'):
                ns = s[:x] + s[x+1:]
                if ns not in visited and calc(ns) < mi:
                    visited.add(ns)
                    ans.extend(dfs(ns))
        return ans
        
    def calc(s):
        a = b = 0
        for c in s:
            a += {'(' : 1, ')' : -1}.get(c, 0)
            b += a < 0
            a = max(a, 0)
        return a + b

    visited = set([s])    
    return dfs(s)
def removeInvalidParentheses(self, s):
    def isvalid(s):
        ctr = 0
        for c in s:
            if c == '(':
                ctr += 1
            elif c == ')':
                ctr -= 1
                if ctr < 0:
                    return False
        return ctr == 0
    level = {s}
    while True:
        valid = filter(isvalid, level)
        if valid:
            return valid
        level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}

二叉树的遍历

二叉树还存在着一些独特的遍历手段：

以及一些围绕这三种遍历方式的问题：

第一，二题比较简单。对于第三题，可以根据二叉搜索树的特性进行中序遍历，因为二叉搜索树的中序遍历即为二叉搜索树的所有节点的排序结果，所以再中序遍历时，得到的第K个结果即为题解。参考代码：

def kthSmallest(self, root, k):
    i=0
    stack=[]
    node=root
    while node or stack:
        while node:
            stack.append(node)
            node=node.left
        node=stack.pop()
        i+=1
        if i==k:
            return node.val
        node=node.right

其他问题

树转图

如果在使用树的过程中，频繁的需要根据子节点获取父节点时，一种做法是为每个子节点添加一个父节点属性，或者干脆就将树转换为无向图来处理。参考问题：

具体解法在《算法笔记——图》中详细介绍。

动态规划

因为树本身的数据结构的限制，一方面，我们得到的是顶点，而不是叶子节点的集合；另一方面，基本的树结构只能从父节点获取子节点，而不能从子节点得到父节点。

这两个特点决定了树状的动态规划问题自底向上的求解是比较困难的，进而就投向了深度遍历的怀抱。或者说是“记忆化搜索”。参考问题：

具体解法在《算法笔记——动态规划》中详细介绍。

参考链接

Share this post:
Share this post on XShare this post on TelegramShare this post via email
Previous Post
算法笔记——动态规划
Next Post
计算器启示录