LeetCodeLink

I have solved this problem weeks ago, but today I completely forgot how I had solved it. As I tried to simulate the interview, I started to think and finally came up with a solution, which is interestingly different from the previous one. That’s what I want to write about this problem, not because it’s difficult or intriguing itself, but because it encouraged me to think twice from different perspective.

My first solution idea is that the problem can be solved by tweaking DFS: inorder traversal. We just need to keep track of the current pointer and the next one.

void dfs(TreeNode* root, TreeNode* next){
if(!root){
return;
}
if(!root->left && !root->right){
root->right = next;
return;
}
else if(root->left){
if(root->right){
dfs(root->left, root->right);
dfs(root->right, next);
}
else{
dfs(root->left, next);
}
root->right = root->left;
root->left=NULL;
}
else{
dfs(root->right,next);
}
}

The other solution I came up today involve return the result as a pair of pointer.

Pair flatten(TreeNode* root){
if(!root){
return Pair(NULL,NULL);
}
if(!root->left && !root->right){
return Pair(root,root);
}
else if(root->left){
Pair left=flatten(root->left);
Pair right=flatten(root->right);
root->left=NULL;
root->right=left.first;
left.second->right=right.first;
if(right.second)
return Pair(root,right.second);
else
return Pair(root,left.second);
}
else{
Pair right = flatten(root->right);
return Pair(root,right.second);
}
}

The two solutions are essential the same, but the point of practicing this problem is thinking path, not memorizing. There are tons of interesting problems come from binary tree, the more I solve, the more intuitive my thinking is.

### Like this:

Like Loading...

*Related*