題目
給定二叉搜尋樹的根結點 root，傳回 L 和 R（含）之間的所有結點的值的和。
二叉搜尋樹保證具有唯一的值。
示例 1：
輸入：root = [10,5,15,3,7,null,18], L = 7, R = 15
輸出：32
示例 2：
輸入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
輸出：23 複制
提示：
樹中的結點數量最多為 10000 個。最終的答案保證小于 2^31。
題解
二叉搜尋樹的特點是左子節點小于父節點，右子節點大于父節點。對于該題，則是求出L <= X <= R之間的節點的和
在處理樹的問題，常使用遞歸 對于遞歸則需要，1. 需要推導遞歸公式， 2. 終止條件 對于該題，遞歸的終止條件則為 目前節點為空，則傳回0，終止遞歸 遞歸公式：目前節點x<L, 則對右子樹的和 目前節點x>R, 則對左子樹的和 目前節點滿足L<=x <= R, 則傳回目前節點值 + 左子樹之和 + 右子樹之和 得到了以上的總結，就可以很容易的寫出實作的代碼
代碼
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rangeSumBST(root *TreeNode, L int, R int) int {
if root == nil {
return 0
}
if root.Val < L {
return rangeSumBST(root.Right, L, R)
}
if root.Val > R {
return rangeSumBST(root.Left, L, R)
}
return root.Val + rangeSumBST(root.Left, L, R) + rangeSumBST(root.Right, L, R)
}
複制
運作結果
總結
遞歸在計算機算法中，比較難懂的一塊。它的處理思想就是将一個問題，分解為一個子問題，該問題具有相同的處理代碼，直到終止條件。遞歸底層使用了棧的資料結構