938, range sum of BST

938, range sum of BST

====

tree, BST

DFS

BFS

====

DFS:

1. 如何開始: 先從root開始

每次都加

node(如果符合range則node->value 否則0), 

node->left, 

node->right

2. 如何結束: 如果本身!node 就return 0

====

class Solution {

public:

  int rangeSumBST(TreeNode* root, int L, int H){

    if(!root) return 0

    return (root->val >= L && root->val <=H ? root->val : 0) + rangeSumBST(root->left, L, H) + rangeSumBST(root->right, L, H)

  }

}

====

BFS:

1. 如何開始: root加到queue, 每次加左子右子

2. 如何停止: queue空

====

class Solution {

public:

  int rangeSumBST(TreeNode* root, int L, int H){

    queue<TreeNode*> pq

    int sum=0

    pq.push(root)

    while(!pq.empty()){

      TreeNode* cur = pq.front

      pq.pop()

      if(cur->val >= L && cur->val <= H)

        sum+=cur->val

      if(cur->left) pq.push(cur->left)

      if(cur->right) pq.push(cur->right)

    }//while pq.empty

  return sum

  }

}