給出一顆二叉搜索樹，求樹中數(shù)值范圍處于[low, high]的節(jié)點(diǎn)之和，DFS，如果當(dāng)前節(jié)點(diǎn)處于[low, high]，則左右子樹都要搜索，如果當(dāng)前節(jié)點(diǎn)小于low，只需要搜索右子樹，如果當(dāng)前節(jié)點(diǎn)大于high，只需要搜索左子樹，不過(guò)這題數(shù)據(jù)比較簡(jiǎn)單，直接深搜完整棵樹，遇到處于[low, high]的節(jié)點(diǎn)就累加也可以過(guò)
只搜索特定子樹：
1 #938
2 #Runtime: 284 ms
3 #Memory: 29.9 MB
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def rangeSumBST(self, root, low, high):
13 """
14 :type root: TreeNode
15 :type low: int
16 :type high: int
17 :rtype: int
18 """
19 def DFS(r):
20 if not r:
21 return 0
22 if r.val >= low and r.val <= high:
23 return r.val + DFS(r.left) + DFS(r.right)
24 if r.val < low:
25 return DFS(r.right)
26 if r.val > high:
27 return DFS(r.left)
28 return DFS(root)
暴力搜完整棵樹：
1 #938
2 #Runtime: 535 ms
3 #Memory: 29.5 MB
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def rangeSumBST(self, root, low, high):
13 """
14 :type root: TreeNode
15 :type low: int
16 :type high: int
17 :rtype: int
18 """
19 self.ans = 0
20 def DFS(r):
21 if not r:
22 return
23 DFS(r.left)
24 if r.val >= low and r.val <= high:
25 self.ans += r.val
26 DFS(r.right)
27 DFS(root)
28 return self.ans