114. 二叉树展开为链表

[hey-monster]

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
 

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [0]
输出：[0]
 

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100
 

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：迭代 + 栈
一边前序遍历（注意需要把修改节点右子节点也放在栈里面保存下来），一边输出

void flatten(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    struct TreeNode* stack[2001];
    int top = 0;
    stack[top++] = root;
    struct TreeNode* prev = NULL;
    while(top > 0){
        struct TreeNode* curr = stack[--top];
        if(prev != NULL){
            prev->left = NULL;
            prev->right = curr;
        }
        struct TreeNode* left = curr->left;
        struct TreeNode* right = curr->right;
        if(right != NULL){
            stack[top++] = right;
        }
        if(left != NULL){
            stack[top++] = left;
        }
        prev = curr;
    }
    return;
}

思路2：寻找前驱节点
空间O(1)的方法
遍历当前节点时，它的右子节点的前一个节点，必然是它的左子树上最右边的节点（即它的前驱节点，相对中序遍历来说）
1、左子树为空，不用变，继续遍历下一节点
2、左子树不为空，则找左子树中最右边的点

//寻找前驱节点
void flatten(struct TreeNode* root){
    struct TreeNode* curr = root;
    while(curr != NULL){
        if(curr->left != NULL){   //左子节点不为空，找左子树的最右边节点，即它的前驱节点
            struct TreeNode* next = curr->left;
            struct TreeNode* preNode = next;
            while(preNode->right != NULL){
                preNode = preNode->right;
            }
            preNode->right = curr->right;
            curr->left = NULL;
            curr->right = next;
        }       //左子节点为空，则不用变，接着遍历下一个节点
        curr = curr->right;
    }
    return;
}