<数据结构/算法> leetcode hot100系列. 114. 二叉树展开为链表

[LeetCode hot 100] 128. 将有序数组转化为二叉搜索树

题目链接

这个题有点意思，乍一看挺简单，想一下就会发现有点点坑。

展开的结果是先序遍历的顺序，也就是说对于某个节点，展开后它的右子树这一串应该是根节点→左子树→右子树这个顺序，而左子树和右子树也是这样展开的。

所以对一个节点，我们首先要将左子树链到右子树中，再对左右子树都执行这个操作。这个过程的实现方法叫做Morris遍历，方法是找到左子树的最右节点，再将右子树接到该节点的下面。这玩意的正确性我不会证明，但是可以画一条$y=-x$的斜线，这个过程就相当于沿着这个方向一层一层剥开。知乎上找到一个挺好的示意图

每次把左子树连到右子树之后，需要再对左子树内也进行同样的操作，但是此时左子树就是我们根节点的右孩子，因此把指针移动到右孩子，重复这个循环。此外，右子树也需要执行这个操作，同样不用担心，指针一直往右移动，早晚会指向原本的右子树的根节点，也就是原来的右孩子。代码实现如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while(cur){
            TreeNode* leftRight = cur->left;
            if(leftRight){
                while(leftRight->right){
                    leftRight = leftRight->right;
                }
                leftRight->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;       
        }
    }
};