查找范围中包含的最大子树的大小

这是最近的一个面试问题。要求查找包含在[x, y]范围内的BST的最大子树的大小的问题是x < y。 BST被递归地定义，其中每个节点具有整数值，左子节点和右子节点。我只能找到树中位于范围内的节点总数，但无法找到最大的子树。下面是我使用的代码，在蟒蛇：查找范围中包含的最大子树的大小

def solution(x, y, T): 
    if T is None: 
     return 0 
    size = 0 
    if x < T.val: 
     size += solution(x, y, T.left) 
    if x <= T.val and y >= T.val: 
     size += 1 
    # The following if statement was my attempt at resetting the count 
    # whenever we find a node outside the range, but it doesn't work 
    if x > T.val or y < T.val: 
     size = 0 
    if B > T.x: 
     size += solution(A, B, T.right) 
    return size

的解决方案应该是O(N)其中N是树中的节点的数量。

来源

2016-11-07 JJTsai

随着BST每一个节点，你可以为它说[Li,Ri]，这意味着相关联的有效范围，在该节点谎言的子树的所有元素在有效范围内。

您可以轻松地递归定义这些范围：

对于节点i假设范围[Li, Ri]并存储在该节点的值是val。对于左边的孩子i，范围是[Li, val − 1]。同样对于右边的孩子，范围是[val + 1, Ri]。

对于根节点，有效范围是[−inf, inf]。

来源

2016-11-07 06:34:20

我们可以递归地解决这个问题。我们需要知道每个子树的左边界和右边界（即最小和最大的元素）。如果它位于范围[x，y]中，我们可以用当前子树的总大小来更新答案。下面是一些代码（solution函数返回一个元组，其中包含一些额外的答案信息，如果只想返回范围内最大子树的大小，可以将它包装起来并用作辅助函数）。

def min_with_none(a, b): 
    """ 
    Returns the minimum of two elements. 
    If one them is None, the other is returned. 
    """ 
    if a is None: 
     return b 
    if b is None 
     return a 
    return min(a, b) 


def max_with_none(a, b): 
    """ 
    Returns the maximum of two elements. 
    If one them is None, the other is returned. 
    """ 
    if a is None: 
     return b 
    if b is None: 
     return a 
    return max(a, b) 


def solution(x, y, T): 
    """ 
    This function returns a tuple 
    (max size of subtree in [x, y] range, total size of the subtree, min of subtree, max of subtree) 
    """ 
    if T is None: 
     return (0, 0, None, None) 

    # Solves the problem for the children recursively 
    left_ans, left_size, left_min, _ = solution(x, y, T.left) 
    right_ans, right_size, _, right_max = solution(x, y, T.right) 

    # The size of this subtree 
    cur_size = 1 + left_size + right_size 

    # The left border of the subtree is T.val or the smallest element in the 
    # left subtree (if it's not empty) 
    cur_min = min_with_none(T.val, left_min) 

    # The right border of the subtree is T.val or the largest element in the 
    # right subtree (if it's not empty) 
    cur_max = max_with_none(T.val, right_max) 

    # The answer is the maximum of answer for the left and for the right 
    # subtree 
    cur_ans = max(left_ans, right_ans) 
    # If the current subtree is within the [x, y] range, it becomes the new answer, 
    # as any subtree of this subtree is smaller than itself 
    if x <= cur_min and cur_max <= y: 
     cur_ans = cur_size 

    return (cur_size, cur_ans, cur_min, cur_max)

该溶液显然线性时间运行，因为它访问每一个节点仅一次，并执行每节点的操作的常数。

来源

2016-11-07 09:57:29 kraskevich

比方说，我们的大小函数返回了一个无效子树的-1。如果节点的值和其子树中的所有值都在范围内，则（子）树是有效的。

# returns a tuple: (size of T, best valid size among itself and its subtrees) 
def f(x,y,T): 
    if T is None: 
    return (0,0) 

    l_size, l_best = f(x,y,T.left) 
    r_size, r_best = f(x,y,T.right) 

    if x <= T.value <= y and l_size >= 0 and r_size >= 0: 
    return (1 + l_size + r_size,1 + l_size + r_size) 
    else: 
    return (-1,max(l_best,r_best))

来源

2016-11-07 11:07:32

查找范围中包含的最大子树的大小

回答

相关问题