1038, binary search tree to greater sum tree

1038, binary search tree to greater sum tree

====

tree, BST

====

試想一下一個BST: [4,1,6]

GreaterSum就是 [4+6, 1+4+6, 6], 也就是固定先加總右子 >>> 再來node >>> 再來左子

1. 如何開始: root開始, 照右>中>左

2. 如何結束: 當!node就return, 終究走完

====

class Solution {

public:

  TreeNode* BstToGst(TreeNode* root){

    int sum=0

    SumNode(root, &sum)

    return root

  }

  void SumNode (TreeNode* node, int& sum){

    if(node == NULL) return

    SumNode(node->right, sum)

    sum+=node->val

    node->val = sum

    SumNode(node->left, sum)

  }

}

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

  }

}