/*
 * 演算法 / Algorithm:
 * 對每個節點 cur，若有左子樹，找左子樹最右節點 pre，把 cur 的右子樹接到 pre->right，
 * 再把左子樹移到右邊並清空左指標。原地完成，O(1) 額外空間。
 * For each node cur with a left subtree, find the left subtree's rightmost node pre,
 * hang cur's right subtree off pre->right, then move the left subtree to the right
 * and clear the left pointer. Done in place with O(1) extra space.
 */

// LeetCode 已定義 TreeNode / TreeNode is predefined by LeetCode.
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;             // cur 指向目前處理的節點 / cur points at the node we process now
        while (cur != nullptr) {          // nullptr 是 C++ 的空指標 / nullptr is C++'s null pointer literal
            if (cur->left != nullptr) {   // 有左子樹才需要搬動 / only rewire when a left subtree exists
                TreeNode* pre = cur->left;      // 從左子樹的根出發 / begin at the left subtree's root
                while (pre->right != nullptr) { // 沿著 right 一直往下 / follow right to the bottom
                    pre = pre->right;     // pre 停在左子樹最右節點（前序最後一個）/ pre lands on the rightmost node (last in pre-order)
                }
                pre->right = cur->right;  // 舊的右子樹接到左子樹尾端 / splice the old right subtree onto the tail
                cur->right = cur->left;   // 左子樹移到右邊 / left subtree becomes the right subtree
                cur->left = nullptr;      // left 依規定清空 / clear left as the problem requires
            }
            cur = cur->right;             // 前進到下一個（前序）節點 / move to the next pre-order node
        }
    }
};