查找範圍中包含的最大子樹的大小

這是最近的一個面試問題。要求查找包含在[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

查找範圍中包含的最大子樹的大小

回答

相關問題