938. 二叉搜索樹的範圍和

• 2019 年 10 月 7 日
• 筆記

題目

給定二叉搜索樹的根結點 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)  }  

運行結果

總結

遞歸在電腦演算法中，比較難懂的一塊。它的處理思想就是將一個問題，分解為一個子問題，該問題具有相同的處理程式碼，直到終止條件。遞歸底層使用了棧的數據結構