Question
Given a binary tree, flatten it to a linked list in-place.
Difficulty:Medium
Category:Tree, Depth-first-Search
Solution
思路是先利用DFS的思路找到最左子节点,然后回到其父节点,把其父节点和右子节点断开,将原左子结点连上父节点的右子节点上,然后再把原右子节点连到新右子节点的右子节点上,然后再回到上一父节点做相同操作。
class Solution {
public:
void flatten(TreeNode* root) {
if (!root) return;
if (root->left) flatten(root->left);
if (root->right) flatten(root->right);
TreeNode* temp = root->right;
root->right = root->left;
root->left = nullptr;
while (root->right) root = root->right;
root->right = temp;
}
};