PTA6-2 查找二叉排序树

题目描述：

给定一棵二叉排序树和一个值，求该值在树中出现的次数。

输入格式：

第一行包含整数 n，表示树中节点个数。

接下来 n 行，每行包含一个整数，表示当前节点的值。

最后一行包含一个整数x，表示需要统计出现次数的值。

输出格式：

共一行，包含一个整数，表示该值在树中出现的次数。

输入样例：

5
2
1
2
3
4
2

输出样例：

2

算法1：

递归遍历，统计值出现的次数。

时间复杂度

平均时间复杂度为O(logn)，最坏时间复杂度为O(n)。

参考文献

Python 代码

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):

    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: bool
        """
        if not root:
            return 0

        if val == root.val:
            return 1 + self.searchBST(root.left, val) + self.searchBST(root.right, val)
        elif val < root.val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

算法2：

迭代遍历，统计值出现的次数。

时间复杂度

平均时间复杂度为O(logn)，最坏时间复杂度为O(n)。

参考文献

Python 代码

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):

    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: bool
        """
        if not root:
            return 0

        count = 0
        stack = [root]

        while stack:
            node = stack.pop()
            if node.val == val:
                count += 1
            if node.left and node.val >= val:
                stack.append(node.left)
            if node.right and node.val <= val:
                stack.append(node.right)

        return count