【LeetCode】【Kotlin】 235.Lowest Common Ancestor of a Binary Search Tree

要找離p、q兩個節點最近的共同祖先(ancestor)

方法一 : 從上面的 root 開始往下找

依據二元搜尋樹特性，節點左子樹所有節點的值會小於它，右子樹所有節點的值會大於它。

程式碼

class Solution {
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        var root = root
        val valueP = p!!.`val`
        val valueQ = q!!.`val`
        while(root != null){
            if (valueP > root.`val` && valueQ > root.`val`) {
                root = root.right
            } else if (valueP < root.`val` && valueQ < root.`val`) {
                root = root.left
            } else {
                return root
            }
        }
        return root
    }
}

也可以寫成下面這樣，不過效果並沒有比較好:

class Solution {
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        var root = root
        val maxValue = if (p!!.`val` > q!!.`val`)  p!!.`val` else q!!.`val`
        val minValue = if (p!!.`val` < q!!.`val`)  p!!.`val` else q!!.`val`

        while(root != null){
            if (minValue > root.`val`) {
                root = root.right
            } else if (maxValue < root.`val`) {
                root = root.left
            } else {
                return root
            }
        }
        return root
    }
}

改良版 : 考慮一開始左或右子樹就是root的情況

class Solution {
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        var root = root
        val maxValue = if (p!!.`val` > q!!.`val`)  p!!.`val` else q!!.`val`
        val minValue = if (p!!.`val` < q!!.`val`)  p!!.`val` else q!!.`val`

        if (root == null || root?.`val` == maxValue || root?.`val` == minValue) return root
        while(root != null){
            if (minValue > root.`val`) {
                root = root.right
            } else if (maxValue < root.`val`) {
                root = root.left
            } else {
                return root
            }
        }
        return root
    }
}