For example,
Given
1 / \ 2 5 / \ \ 3 4 6The flattened tree should look like:
1 \ 2 \ 3 \ 4 \ 5 \ 6Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
Solution: two ways to solve this problem recursively. The first way is: flatten the left and right subtrees first, and then append the flattened right subtree to the right child of the flattened left subtree; at the very last append the head of the flattened left subtree to the right child of the root and set the left child of the root to null; The second way is, as noticed, each node's right child points to the next node of a pre-order traversal in the flattened tree.
/*******************************SOLUTION 1***********************************/
Solution: two ways to solve this problem recursively. The first way is: flatten the left and right subtrees first, and then append the flattened right subtree to the right child of the flattened left subtree; at the very last append the head of the flattened left subtree to the right child of the root and set the left child of the root to null; The second way is, as noticed, each node's right child points to the next node of a pre-order traversal in the flattened tree.
/*******************************SOLUTION 1***********************************/
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void flatten(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function if((root==NULL) || (root->left==NULL&&root->right==NULL)) return; TreeNode* rchild = root->right; TreeNode* ltail = NULL; if(root->left!=NULL){ flatten(root->left); root->right = root->left; ltail = root->left; while(ltail->right!=NULL) ltail = ltail->right; } root->left = NULL; if(rchild!=NULL){ flatten(rchild); if(ltail!=NULL){ ltail->right = rchild; } else root->right = rchild; } } };/*******************************SOLUTION 2***********************************/
class Solution { public: void flattenHelper(TreeNode* root, TreeNode* &head){ if(root!=NULL){ flattenHelper(root->right, head); flattenHelper(root->left, head); root->right = head; root->left = NULL; head = root; } } void flatten(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function TreeNode* head = NULL; flattenHelper(root, head); } };
No comments:
Post a Comment