此题的关键部分就是如何处理 右儿子如何连接在左儿子上，然后再由左儿子变成父亲的右儿子。
现假设为一种最简单的情况：
O (a)
/ \
O (b) O (c)
显然，节点 c 需要的得到的点是节点 b
O (a)
/ \
O (b) O (c)
\
O (d)
节点 c 需要的点是节点 d.
所以，对于当前父亲节点，其左儿子中最右下的那个值，就是其右儿子的前驱。如果左儿子没有往右的值，最左下的值就是右儿子的前驱。
还是代码解释的清楚：
class Solution { public: void flatten(TreeNode* root) { auto _ = solve(root); } TreeNode *solve(TreeNode *root) { if(root == nullptr) return root; auto retLef = solve(root -> left); auto retRig = solve(root -> right); if(retLef) { retLef -> right = root -> right; root -> right = root -> left; root -> left = nullptr; } return retRig ? retRig : (retLef ? retLef : root); // 返回的值为兄弟节点的前驱 } };
再贴一个官方的：
class Solution { public: void flatten(TreeNode* root) { TreeNode *curr = root; while (curr != nullptr) { if (curr->left != nullptr) { auto next = curr->left; auto predecessor = next; while (predecessor->right != nullptr) { predecessor = predecessor->right; } predecessor->right = curr->right; curr->left = nullptr; curr->right = next; } curr = curr->right; } } };