[leetcode/lintcode 題解]算法面試真題詳解：二叉搜尋樹結點最小距離

描述

給定一個二叉搜尋樹的根結點 root, 傳回樹中任意兩節點的差的最小值。

• 二叉樹的大小範圍在 2 到 100。
• 二叉樹總是有效的，每個節點的值都是整數，且不重複。

線上評測位址：

領扣題庫官網

樣例1
輸入: root = {4,2,6,1,3}
輸出: 1
解釋:
注意，root是樹結點對象(TreeNode object)，而不是數組。

給定的樹 [4,2,6,1,3,null,null] 可表示為下圖:

          4
        /   \
      2      6
     / \    
    1   3  

最小的內插補點是 1, 它是節點1和節點2的內插補點, 也是節點3和節點2的內插補點。           

樣例2
輸入: root = {2,1}
輸出: 1
解釋:
注意，root是樹結點對象(TreeNode object)，而不是數組。

給定的樹 {2,1} 可表示為下圖:

      2
     / 
    1 

最小的內插補點是 1, 它是節點1和節點2的內插補點。           

解題思路

二叉搜尋樹，根據樹的性質，知道root的右子樹都是大于它的，左子樹都是小于它的。

那麼如果做中序周遊，标準的做法是得到一個遞增的序列。

我們就先周遊左根，節點，右根，這樣就會得到一個遞增的序列。

然後對這個序列相鄰相減，取最小值即可。 實作時，可以優化掉這個序列。

在周遊時記錄上一個通路的節點值，和目前節點相減，記錄下最小值即可。

源代碼

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root:  a Binary Search Tree (BST) with the root node
    @return: the minimum difference
    """
    pre = -float('inf')
    res = float('inf')

    def minDiffInBST(self, root):
        # Write your code here.
    
        if root.left:
            self.minDiffInBST(root.left)
        self.res = min(self.res, root.val - self.pre)
        self.pre = root.val
        if root.right:
            self.minDiffInBST(root.right)
        return self.res
           

更多題解參考：

九章官網solution