数据结构 -- 树

二叉搜索树

二叉搜索树，也称有序二叉树、排序二叉树，指的是一颗空树且具有下列特征的树：

• 左子树上所有节点的值均小于它的根节点的值
• 右子树上所有节点的值均大于它的根节点的值
• 依次类推：左、右子树也分别为二叉查找树
  所以中序遍历（也是升序遍历）

二叉搜索树的查询和插入时间复杂度都是 O(logn)

树的面试题解法一般都是递归，为什么？

首先可以使用递归来解决的问题，一般具有如下特点：

• 1. 该问题可以被分解成若干个重复的子问题；
• 2. 该问题与它分解出的子问题可以使用相同的算法来解决；
• 3. 有明确的终止条件 树这种数据结构的特点和上述三个特点高度一致，一棵树的每个非叶子节点的子节点也都是一棵树，都是树自然可以使用相同的算法来处理，因为没有环所以天然具有终止条件。
• 另外一方面，树本身是一种非线性的数据结构，循环遍历不易。当然循环遍历也是可以做，树是一种特殊的图，我们完全可以使用图的广度优先遍历算法一层一层的循环遍历整棵树。
• 综上，我们一般还是选择递归的方式来解决树的问题。

二叉树的遍历方法：前序、中序、后序

以下附上模板

class Solution(object):
    def __init__(self):
        self.traverse_path = None

    # 前序  根左右
    def preorder(self, root):
        if root:
            self.traverse_path.append(root.val)
            self.preorder(root.left)
            self.preorder(root.right)

    # 中序  左根右
    def inorder(self, root):
        if root:
            self.inorder(root.left)
            self.traverse_path.append(root.val)
            self.inorder(root.right)

    # 后序  左右根
    def postorder(self, root):
        if root:
            self.postorder(root.left)
            self.postorder(root.right)
            self.traverse_path.appen

下面给出几道典型题目进行分析哈：

给定一个二叉树，返回它的中序 遍历。leetcode 94

下面的解法，都是仿照上面模板进行写的，大家都可以去试着找一些前序遍历后续遍历的题，至于为啥用递归解法，上面也已经说了。

复杂度分析

• 时间复杂度：O(n)。递归函数 T(n) = 2 \cdot T(n/2)+1T(n)=2⋅T(n/2)+1。
• 空间复杂度：最坏情况下需要空间O(n)，平均情况为OO(logn)。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        def helper(root):
            if not root:
                return
            helper(root.left)
            res.append(root.val)
            helper(root.right)
        helper(root)
        return res

思考

二叉树能实现增删查的功能，而散列表则可以更加高效的完成这些操作，为什么还要有二叉搜索树这样的数据结构呢？

• 第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
• 第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
• 第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
• 第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
• 最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。
• 综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一个。