Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.
Example 1: Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8 / / \ 1 7 9 Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9
Constraints:
- The number of nodes in the given tree will be between
1
and100
. - Each node will have a unique integer value from
0
to1000
.
A:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* increasingBST(TreeNode* root) { if(!root) return root; TreeNode * left = root->left; root->left = nullptr; TreeNode * newRoot= root; if(left){ newRoot = increasingBST(left); TreeNode *tail = newRoot; while(tail->right) tail = tail->right; tail->right = root; } root->right = increasingBST(root->right); return newRoot; } };
NOTE:
上面有个跑到最左边的while loop,这样是很不好的。
因此我改进了下: 每次返回一个最左边和最右边的数组
class Solution { private: vector<TreeNode*> helper(TreeNode* root){ vector<TreeNode*> res; if(!root){ return res; } auto resLeft = helper(root->left); auto resRight = helper(root->right); root->left = NULL; if(!resLeft.empty()){ resLeft.back()->right = root; res.push_back(resLeft.front()); } res.push_back(root); if(!resRight.empty()){ root->right = resRight.front(); res.push_back(resRight.back()); } return res; } public: TreeNode* increasingBST(TreeNode* root) { vector<TreeNode*> res = helper(root); return res.size()?res[0]:NULL; } };
然而,这样效率上已经挺高了。可是依然被很多给beat了。
再改进下:每次更新之前留下的最右边的那个指针(作为参数)。 然后返回最左边的指针。
注意: 这里,花了我快1个小时,就是C++语法的的锅
改进是: 每次返回最左边的root,但是,有一个跟随的指针的指针(double pointer)
来记录每次的最右边的ancestor (previous) node.
一开始自己只用了一层指针,是不对的。
class Solution { private: TreeNode* inorder(TreeNode* root, TreeNode** ppre){ // root is not nullptr TreeNode* newRoot = root; if(root->left){ newRoot = inorder(root->left, ppre); root->left = nullptr; } (*ppre)->right = root; *ppre = (*ppre)->right; if(root->right){ inorder(root->right, ppre); } return newRoot; } public: TreeNode* increasingBST(TreeNode* root) { TreeNode* dummy = new TreeNode(); if(!root) return root; return inorder(root, &dummy); } };
No comments:
Post a Comment