[LeetCode] 538. Convert BST to Greater Tree

轉自LeetCode

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

<Solution>

想法如下

• 這題的主要關鍵在於，是要把所有比自己數字大的數字和自身加起來，而BST的特性是，在右子樹的都一定比自身大，在左子樹的都一定比自身小

• 因此，對BST採用 右 -> 根 -> 左 的方式去歷遍，並且同時累加數字，歷遍完即可

code 如下

C++

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* convertBST(TreeNode* root) {
	int sum = 0;
	convert(root, sum);
	return root;
	}
	void convert(TreeNode *root, int &sum) {
	if(root == NULL) {
	return;
	}
	convert(root->right, sum);
	sum += root->val;
	root->val = sum;
	convert(root->left, sum);
	}
	};

view raw convertBstToGreaterTree.cpp hosted with ❤ by GitHub