class Solution { public: void flatten(TreeNode* root) { if (root == nullptr) return; // 先展开左右子树 flatten(root->left); flatten(root->right); // 保存右子树 TreeNode* right = root->right; // 将左子树移到右边 root->right = root->left; root->left = nullptr; // 找到当前右子树的末尾 TreeNode* p = root; while (p->right) { p = p->right; } // 将原来的右子树接上 p->right = right; } };
class Solution { public: void flatten(struct TreeNode* root) { struct TreeNode* cur = root; while (cur != NULL) { if (cur->left != NULL) { // 找到当前节点左子树的最右节点（也就是cur节点的前驱节点） struct TreeNode* next = cur->left; // 保存左节点 struct TreeNode* predecessor = next; while (predecessor->right != NULL) { predecessor = predecessor->right; } // 将当前节点的右子树接到前驱节点的右子树上 predecessor->right = cur->right; // 将当前节点的左子树移到右子树位置 cur->right = next; cur->left = NULL; // 左子树置为NULL } // 继续处理下一个节点 cur = cur->right; } } };
