二分查找，二叉搜索樹尋找最近祖先均是典型分治問題，把原問題分成三部分考慮，遞歸實現簡單，迭代實現也比較簡單,里面蘊含了一些從從遞歸到迭代的技巧，注意這里沒有使用模擬棧技術。

深究其原因是，這一類型的遞歸，每次查找丟棄了一半，遞歸到底部就找到了問題的解，搜索到最小子問題就解決了問題，類似于分支限界剪枝，剪到最后就是問題的解，不需要一層一層的回退，也就沒有必要使用棧來恢復現場。

二分查找，遞歸和迭代

# 注意遞歸的返回值，遞歸的要返回的話，要前后一致，或者直接基于某一層考慮，把遞歸看成結果 def binary_Serach_recursive(arr,left,right,target):middle = (left + right) // 2# 遞歸出口if left > right :return(-1)if arr[middle] == target:return(middle)elif arr[middle] < target:# 這里沒有return的話，結果就沒法return出來return binary_Serach_recursive(arr,middle+1,right,target)else:return binary_Serach_recursive(arr,left,middle-1,target)# 遞歸轉換為迭代實現：可以看出上述的遞歸就是，left,right對應一個子問題，left,right兩個指針相互逼近的過程 # 迭代實現時，也不斷逼近兩個指針，即可迭代實現遞歸 def binary_Serach_iterative(arr,target):left = 0right = len(arr)-1# 循環體條件while left <= right:middle = (left + right) // 2if arr[middle] == target:return middleelif arr[middle] < target:left = middle +1else:right = middle -1return -1

二叉搜索樹尋找最近祖先,遞歸和迭代

def lowestCommonAncestor(self, root, p, q):if root.data < p and root.data < q:return self.lowestCommonAncestor(root.right, p, q)elif root.data > p and root.data > q:return self.lowestCommonAncestor(root.left, p, q)else:return root # 樹形結構，是使用一個指針就可以描述一個子問題，指針對應的是子問題的選擇，迭代時更新 # 樹形指針就行了，出口就是找到了祖先，或者樹形指針指向None# 這里是樹形指針的一種用方法，是把遞歸轉化為迭代的一種常用方法 def lowestCommonAncestorRecursion(self, root, p, q):pointer = rootwhile pointer:if pointer.data < p and pointer.data < q:pointer = pointer.rightelif pointer.data > p and pointer.data > q:pointer = pointer.left else:return pointer 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的树形结构：从二分查找，二叉搜索树寻找最近祖先，从递归到迭代，实现技巧总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。