「我懂了，但是我暫時不想再看到翻轉或是回文問題了。」學妹說著打了幾個噴嚏。

「可能還是著涼了，我去浴室弄條熱毛巾給妳。」今早的三明治感覺是從冰箱裡拿出來的，冰涼涼的給不了溫暖。離午餐時間又還早，只好先用熱毛巾應付。

學妹感受了一會兒熱氣，精神一振：「我好多了，學姊說說要挑戰的新題目類型吧。」

「嗯，接下來要挑戰Tree，妳有玩過遊戲吧？和技能樹的那個結構很像。」教授上課的時候是用家庭樹舉例，但是現在的小朋友對家譜興趣不大吧。

學妹馬上回應：「是說要得到高級技能前要先取得低級技能的那個嗎？」

「對，每個技能都是一個節點，而每個節點分支出更多的節點。」雖然說有些遊戲複雜的技能樹其實比較偏有向無環圖，讓技能可以從多個路線取得。不過為了避免讓學妹弄糊塗就不現在提出來了。

我手指沾著水在矮桌上畫了一個圓圈，「這是初始節點Root，」從圓圈下方畫出兩條像觸角的線，「這是往下的分支，」然後線的尾端畫上圓圈。「這是被稱為Children的節點。」我又在Root多畫了幾條線。「分支可以不只一個，也可以沒有分支。沒有分支的終點被稱為Leaf。」

「真奇怪的圖形。」學妹看著我的塗鴉，不客氣的評價。

「嗯⋯⋯是呀，不過會有這樣的圖形graph留下來考試，就代表這是有優點的設計結構。」我心裡估算了下時間。「嗯，要不我們馬上來實戰吧。」

我挑了一題很簡單的題目2236. Root Equals Sum of Children，檢查所有Children加總的結果是不是相等於Root的值。

「嗯？回答格子裡有Example耶。」

學妹第一次看到回答格子有類型說明，我倒是習慣了。

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */

「大概是考慮到有人不知道TreeNode的結構吧。妳看這樣的結構是不是最多就是兩個分支？這種樹有個專有名詞——二元樹。」

「真的欸，所以就因為只有兩個分支，直接用左右稱呼了啊。」

「對，然後初始參數val旁邊有兩個重音符，是因為命名和Kotlin本來就有的狀態保留字衝突到了，所以要另外包起來。」

「我以為把變數名稱變短是為了節省打字時間，但是還要加上兩個重音符好像也沒比較快。」學妹一眼就認出val是value的縮寫。

「這個妳要問設計的工程師哈哈。好了，我們直接寫這題吧，別忘記還有時間限制呢。」

果然這種題目對學妹來說很簡單，她很快就寫出了答案。甚至還用了lambda系列的run來省去頻繁的Null判斷。

class Solution {
   fun checkTree(root: TreeNode?): Boolean {
       return root?.`val` ?: 0 == (root?.left?.`val` ?: 0) + (root?.right?.`val` ?: 0) ?: true
   }
}

「真沒挑戰性，而且也看不到Tree有什麼優點。」學妹碎碎念。

「這樣啊，那就來看看BST二元搜尋樹的題目吧。」我打開了準備好的938. Range Sum of BST，同樣是求Children加總的結果，但是Children有條件限制。

「感覺和剛剛沒什麼差別呀？除了比較比較多層。」學妹很快寫好了她的答案。

class Solution {
    fun rangeSumBST(root: TreeNode?, low: Int, high: Int): Int {
        return root?.run { 
             rangeSumBST(left, low, high) + rangeSumBST(right, low, high) + if(`val` in low..high) `val` else 0
        }  ?: 0
    }
}

「哦哦，用上了遞迴啊。」遞迴就是自己裡面呼叫了自己，用在這裡倒是合適。「可是有白做工的地方唷。」

「啊？哪裏？」學妹檢查了自己的程式碼，沒看出問題。

「因為妳沒注意到BST的特性呀。BST的特性就是左下的Children一定小於Parent節點，右下的Children則是相反，必須大於Parent節點。」我提示她。

學妹看了題目上的樹，同意了我的說法。「真的耶，但這和白做工有什麼關係？」

「按照BST的特性，最小值就在最左下的地方。如果確定Parent節點已經小於要求的條件了，那就沒必要往左下跑了吧？」我只好把話說明白。

「啊！」學妹終於恍然大悟，馬上修改了程式碼。

class Solution {
    fun rangeSumBST(root: TreeNode?, low: Int, high: Int): Int {
        return root?.run { 
            when {
                `val` < low -> rangeSumBST(right, low, high)
                `val` > high -> rangeSumBST(left, low, high)
                else -> `val` + rangeSumBST(left, low, high) + rangeSumBST(right, low, high)
            }
        } ?: 0
    }
}