給定二叉搜索樹的根結點 root，返回值位于范圍 [low, high] 之間的所有結點的值的和。

示例 1：

輸入：root = [10,5,15,3,7,null,18], low = 7, high = 15
輸出：32
示例 2：

輸入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
輸出：23

解題思路

在遞歸的過程中，利用二叉搜索樹的性質進行剪枝，例如當前遞歸的節點值是10，而搜索的范圍是[11,20],因此就不需要遍歷左子樹了，因為左子樹上所有的值都比當前的值要小。

代碼

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func rangeSumBST(root *TreeNode, low int, high int) int {res:=0if root==nil{return res}if root.Val>=low{res+=rangeSumBST(root.Left,low,high)}if root.Val>=low&&root.Val<=high{res+=root.Val}if root.Val<=high{res+=rangeSumBST(root.Right,low,high)}return res
}

提交結果

優化思路

主要思路還是上面那樣，但是程序邏輯進行了修改，當前節點不在搜索范圍內的時候，直接返回左子樹或者右子樹的結果，不需要再像原來的代碼一樣，需要一個變量存儲左右子樹的返回值，并且判斷當前節點是否在范圍內，再決定是否將當前節點的值進行累加

代碼

func rangeSumBST(root *TreeNode, low int, high int) int {if root==nil{return 0}if root.Val<low{return  rangeSumBST(root.Right,low,high)}if root.Val>high{return  rangeSumBST(root.Left,low,high)}return root.Val+ rangeSumBST(root.Left,low,high)+rangeSumBST(root.Right,low,high)
}

優化后

給定二叉搜索樹的根結點?root，返回值位于范圍 [low, high] 之間的所有結點的值的和。

示例 1：

輸入：root = [10,5,15,3,7,null,18], low = 7, high = 15
輸出：32
示例 2：

輸入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
輸出：23

解題思路

在遞歸的過程中，利用二叉搜索樹的性質進行剪枝，例如當前遞歸的節點值是10，而搜索的范圍是[11,20],因此就不需要遍歷左子樹了，因為左子樹上所有的值都比當前的值要小。

代碼

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func rangeSumBST(root *TreeNode, low int, high int) int {res:=0if root==nil{return res}if root.Val>=low{res+=rangeSumBST(root.Left,low,high)}if root.Val>=low&&root.Val<=high{res+=root.Val}if root.Val<=high{res+=rangeSumBST(root.Right,low,high)}return res
}

提交結果

優化思路

主要思路還是上面那樣，但是程序邏輯進行了修改，當前節點不在搜索范圍內的時候，直接返回左子樹或者右子樹的結果，不需要再像原來的代碼一樣，需要一個變量存儲左右子樹的返回值，并且判斷當前節點是否在范圍內，再決定是否將當前節點的值進行累加

代碼

func rangeSumBST(root *TreeNode, low int, high int) int {if root==nil{return 0}if root.Val<low{return  rangeSumBST(root.Right,low,high)}if root.Val>high{return  rangeSumBST(root.Left,low,high)}return root.Val+ rangeSumBST(root.Left,low,high)+rangeSumBST(root.Right,low,high)
}

優化后