daily pastebin goal
28%
SHARE
TWEET

Untitled

a guest Feb 16th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     int rangeSumBST(const TreeNode* root, int L, int R) {
  13.         return L > R ? 0
  14.             : L == R ? sU(root, L)
  15.             : sLR(root, L, R);
  16.     }
  17.  
  18.     int sLR(const TreeNode* n, int L, int R) {
  19.         return n == nullptr ? 0
  20.             : n->val >  R ? sLR(n->left, L, R)
  21.             : n->val == R ? n->val + sL(n->left, L)
  22.             : n->val <  L ? sLR(n->right, L, R)
  23.             : n->val == L ? n->val + sR(n->right, R)
  24.             : n->val + sLR(n->left, L, R) + sLR(n->right, L, R);
  25.     }
  26.  
  27.     int sR(const TreeNode* n, int R) {
  28.         return n == nullptr ? 0
  29.             : n->val >  R ? sR(n->left, R)
  30.             : n->val == R ? n->val + s(n->left)
  31.             : n->val + sR(n->left, R) + sR(n->right, R);
  32.     }
  33.  
  34.     int sL(const TreeNode* n, int L) {
  35.         return n == nullptr ? 0
  36.             : n->val <  L ? sL(n->right, L)
  37.             : n->val == L ? n->val + s(n->right)
  38.             : n->val + sL(n->left, L) + sL(n->right, L);
  39.     }
  40.  
  41.     int s(const TreeNode* n) {
  42.         return n == nullptr ? 0 : n->val + s(n->left)  + s(n->right);
  43.     }
  44.    
  45.     int sU(const TreeNode* n, int U) {
  46.         return n == nullptr ? 0
  47.             : n->val < U ? sU(n->right, U)
  48.             : n->val > U ? sU(n->left, U)
  49.             : U;
  50.     }
  51. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top