class Solution {
public:
void flatten(TreeNode* root) {
if (!root) return;
if (root>left){
flatten(root>left);
ptr>right = root>right;
root>right = root>left;
root>left = NULL;
}
ptr = root;
flatten(root>right);
}
private:
TreeNode* ptr;
};
Concise C++ recursion solution

class Solution { private: TreeNode *tail; public: void flatten(TreeNode *root) { if (!root) return; tail = root; if (root>left) { flatten(root>left); tail>right = root>right; root>right = root>left; root>left = NULL; } flatten(tail>right); } };
Minor change based on your code.
tail
denotes the last node of the preorder sequence of subtreeroot>left
.The preorder traversal structure is clearer. Visit the root (
tail = root
), then visit left subtree and then right subtree.IMHO, this code is a little bit faster than yours because the line
flatten(root>right);
in your code will result in useless recursive calls.