给定一个二叉树,原地将它展开为链表(右侧路径)。
例如,给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为:
1
\
2
\
3
\
4
\
5
\
6
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
void flatten(TreeNode* root) {
f(root);
}
TreeNode* f(TreeNode* root)//返回的是最底端的节点指针
{
if(!root)
return NULL;
TreeNode *l = f(root->left);
TreeNode *r = f(root->right);
if(!l && !r)
return root;
else if(!l && r)
return r;
else if(l && !r)
{
swap(root->left,root->right);
return l;
}
else
{
swap(root->left,root->right);
l->right = root->left;
root->left = NULL;
return r;
}
}
};