114-二叉树展开为链表

LeetCode 114. Flatten Binary Tree to Linked List

LeetCode-114

Given the root of a binary tree, flatten the tree into a "linked list":

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

method: 递归

左子树和右子树处理完之后，有4种情况

• 无左子树，无右子树
• 无左子树，有右子树
• 有左子树，无右子树
• 有左子树，有右子树

前2种可以直接返回不用处理，后2种需要处理

1. 先记录右子树
2. 把左子树换到右子树
3. 找到右子树的插入位置

void flatten(TreeNode* root) {
    if (!root) return;      // 空节点直接返回
    flatten(root->left);
    flatten(root->right);
    // 运行到这里，说明该节点的左子树和右子树已经处理好了
    if (!root->left) return;    // 左子树为空，就不用处理了，直接返回
    TreeNode *tmp = root->right;    // 记录右子树
    root->right = root->left;       // 左子树换到右边
    root->left = nullptr;           // 断开左指针
    TreeNode *cur = root->right;
    while (cur->right) cur = cur->right;    // 找到可以插入的位置
    cur->right = tmp;
}

改进

先处理右子树，再处理左子树，这样pre就一直指向需要被移过去的最高节点，然后让左子树指向pre就可以了

TreeNode *pre = nullptr;
void flatten(TreeNode* root) {
    if (!root) return;
    flatten(root->right);   // 先处理右子树
    flatten(root->left);
    root->right = pre;
    root->left = nullptr;
    pre = root;
}