Flatten Binary Tree to Linked List DESCRIPTIONIMPLEMENTATION Convert BST to Greater Tree DESCRIPTIONIMPLEMENTATION

114. Flatten Binary Tree to Linked List

DESCRIPTION

Given a binary tree, flatten it to a linked list in-place.

For example,

Given :

1 / \ 2 5 / \ \ 3 4 6

The flattened tree should look like:

1 \ 2 \ 3 \ 4 \ 5 \ 6

This problem changes the tree into a linked list.

My algorithm is below: I use iterative method to do pre-order and store the right node to the stack and point the current node to left-node, set left node to NULL. Do this operation until the stack is empty.

IMPLEMENTATION

The code is below:

/** * 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: void flatten(TreeNode* root) { if(!root) return; stack<TreeNode*> que; TreeNode* cur = root; if(root->right) que.push(root->right); if(root->left) que.push(root->left); while(!que.empty()) { TreeNode* left = que.top(); que.pop(); cur->left = NULL; cur->right = left; if(left->right) que.push(left->right); if(left->left) que.push(left->left); cur = cur->right; } } };

538. Convert BST to Greater Tree

DESCRIPTION

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

This problem is a pre-order problem, from this we can see that the node is the accumulated by its own value and its right sub-tree accumulated value.

So here I change the order of tree with the right node first then its left tree node, and a global value stores the last node value to assign to the newer node.

IMPLEMENTATION

The code shows below:

/** * 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: int last = 0; bool hasValue = false; void findRightSum(TreeNode* root) { if(!root) return; if(root->right) findRightSum(root->right); root->val += last; last = root->val; if(root->left) findRightSum(root->left); } TreeNode* convertBST(TreeNode* root) { if(!root) return root; findRightSum(root); return root; } };