找到二叉樹中的最小值，Python

Question

我想寫一個函數，返回二叉樹中的最小值而不是二叉搜索樹。 這是我寫的，這是不正確的。

def min(root, min_t): # min_t is the initially the value of root 
    if not root: 
      return min_t 

    if root.key < min_t: 
      min_t = root.key 

    min(root.left, min_t) 
    min(root.right, min_t) 

    return min_t 

我覺得我不太瞭解遞歸。我似乎無法弄清楚何時使用遞歸調用的return語句，何時不使用。

感謝您的見解！

這裏有另外一個我想出來的，它的工作原理，但它似乎沒有最有效的：

n = [] 
def min_tree(root, n): 
    if root: 
     n += [(root.key)] 
     min_tree(root.left, n) 
     min_tree(root.right, n) 
    return min(n) 

的思考？

Answer 1

對於這個特定的問題，你想遍歷整個樹並返回最小的值。但總體而言，遞歸的基本原理是，然後再次調用函數，就會出現同樣問題的修改版本。

考慮你的樹：

root 
/ \ 
left right 

當你調用左子樹的遞歸函數，你再次提出了一個樹。因此，你應該能夠使用相同的邏輯。

遞歸函數的關鍵是基本情況和遞歸步驟。在你的樹的例子中，當你找到最小值（你會怎麼知道？）時，基本情況並非如此，而是當你到達樹的底部（又名葉）時。

而且，遞歸步驟是查看每個子問題（bin_min（left）和bin_min（right））。

最後一塊正在考慮返回值。不變的是你的函數已經返回了它所看到的最小元素。因此，當遞歸調用返回時，您知道它是最小的元素，然後您需要返回的是三個可能選項（root，left_min和right_min）中最小的元素。

def min_bin(root): 
    if not root: 
     return MAX_VAL 
    left_min = min_bin(root.left) 
    right_min = min_bin(root.right) 

    return min(left_min, right_min, root.val) 

請注意，這是一個不同於@Rik Poggi的解決方案。他使用尾遞歸進行優化。

Answer 2

因爲您比罐裝解決方案更能從中找出自己的想法，下面是一些提示。首先，你不應該叫它min，因爲當然你不能調用python的min來測試你的結果。而作爲Michael的回答提醒我，你不要有通過min_t，因爲你可以測試root.key而不是 - 但我認爲這有助於通過min_t瞭解問題。

除此之外，你的第一行是正確的;這裏做得很好。 ：

def tree_min(root, min_t): # min_t is the initially the value of root 
    if not root: 
      return min_t 
    if root.key < min_t: 
      min_t = root.key 

現在你必須考慮返回什麼。基本上，有三個可能的最小值。第一個是min_t。第二個是right子樹的最小值。第三個是left子樹的最小值。獲取後兩個值（這是遞歸調用進入的地方），然後返回最小值。

Answer 3

邁克爾的回答解釋了你可能應該解決問題的方式，但他沒有解釋你目前的嘗試有什麼問題。據我瞭解，您的策略是檢查每個節點，並隨時跟蹤最低值，使用遞歸查找所有節點。一旦你檢查了所有的節點，你就知道結果是整個樹的最小值。這是一個非常有效的方法，除非參數不像你期望的那樣工作，否則它會奏效。

Python通過值傳遞參數，而不是通過引用。當使用「min_t = root.key」爲min_t賦值時，它只在函數內部生效。函數的調用者沒有看到新的值。

你可以用一些簡單的代碼測試：

def add_one_to(x): 
    x = x + 1 
    print "add_one_to", x 

x = 2 
add_one_to(x) 
print x 

當您運行X上的功能裏面，但沒有在頂級水平遞增的代碼可以看到。

這也適用於函數自己調用時。每個調用都有自己的一組局部變量，並且分配給函數內的局部變量不會影響調用它的實例。

請注意，某些語言確實允許您通過引用傳遞參數。如果您通過引用傳遞參數，則在函數內部分配該參數也會影響調用者。如果Python是這些語言之一，你可以使min_t成爲引用參數，並且你的函數可以正常工作。

儘管Python不直接支持引用參數，但您也可以將引用參數看作是在調用函數時進入函數的值，並且在函數完成時還將其傳回給調用方。你可以分開做這兩件事。要將值傳回給調用者，請返回該值。調用者然後可以將該函數分配給它的本地，並且基本上通過引用傳遞了一個參數。

這裏是你如何可以申請是上面的例子：

def add_one_to(x): 
    x = x + 1 
    print "add_one_to", x 
    return x 

x = 2 
x = add_one_to(x) 
print x 

只需添加一個返回值和分配，和它的作品，因爲它應該。

你也可以將此你原來的功能：

def min(root, min_t): # min_t is the initially the value of root 
    if not root: 
      return min_t 

    if root.key < min_t: 
      min_t = root.key 

    min_t = min(root.left, min_t) 
    min_t = min(root.right, min_t) 

    return min_t 

我所做的只是在每次調用前加上「min_t =」到MIN（）和改變你的return語句在年底返回min_t。 （我認爲你可能意思是返回min_t，min是你函數的名字，所以這沒什麼意義。）我相信這個版本會起作用。

編輯：儘管如此，你的min_tree函數工作的原因是n是一個列表，列表是可變對象。當我在談論上面的「價值」時，我真正的意思是「對象」。 python中的每個變量名稱映射到一個特定的對象。如果你有這樣的代碼：

def replace_list(x): 
    x = [1, 2, 3] 

x = [2] 
replace_list(x) 
print x 

結果是[2]。所以，如果你用「x =」給x賦一個新的值，調用者就不會看到它。但是，如果這樣做：

def replace_list(x): 
    x.append(1) 

x = [2] 
replace_list(x) 
print x 

結果是[2,1]。這是因爲你沒有改變x的值; x仍指向相同的列表。但是，該列表現在包含一個附加值。不幸的是，「+ =」操作符在這方面令人困惑。你可能會認爲「x + = y」與「x = x + y」相同，但在Python中並不總是這樣。如果「x」是一種支持「+ =」的對象，那麼該操作將修改對象。否則，它將與「x = x + 1」相同。列表知道如何處理「+ =」，所以在列表中使用+ =會對其進行修改，但將其與數字一起使用則不會。

實際上，你可以測試這個而不做任何函數調用：

x = [1, 2] 
y = x 
y += [3] 
print x # [1, 2, 3] 
print y # [1, 2, 3] 
print x is y # True, x and y are the same object, which was modified in place 

x = [1, 2] 
y = x 
y = y + [3] 
print x # [1, 2] 
print y # [1, 2, 3] 
print x is y # False, y is a new object equal to x + [3] 

x = 1 
y = x 
y += 2 
print x # 1 
print y # 3 
print x is y # False, y is a new object equal to x + 2 

Answer 4

這裏是尋找最小元素的遞歸方法：

minelement = float("inf") 
def minimum(self, root): 
    global minelement 
    if root: 
     if root.data < minelement: 
      minelement = root.data 

     self.minimum(root.left) 
     self.minimum(root.right) 
    return minelement