LeetCode 二叉树展开为链表（递归、非递归）

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树
    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

不难发现，本题题目转换链表的访问的顺序是采取先序遍历。
先序遍历：先根节点，再左子树，后右子树
方法一：使用容器将中序遍历的序列保留，然后按照顺序把它们串接起来即可。（时间复杂度O(n)，额外空间复杂度O(n)）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> preOrderRes;
    //先序遍历，并将先序遍历序列保存到preOrderRes
	void myPreOrderTraversal(TreeNode* root) {
		if (root == NULL) {
			return;
		}
        //先访问当前根节点
		preOrderRes.push_back(root);
		//再遍历左子树
		if (root->left != NULL) {
			myPreOrderTraversal(root->left);
		}
		//后遍历右子树
		if (root->right != NULL) {
			myPreOrderTraversal(root->right);
		}
	}
	void flatten(TreeNode* root) {
        if (root == NULL){
            return;
        }
		preOrderRes = vector<TreeNode*>();
        //先序遍历，得到先序遍历序列
        myPreOrderTraversal(root);
        int resSize = preOrderRes.size();
        //按照要求进行拼接
        for (int i = 0; i < resSize - 1; ++i){
            preOrderRes[i]->left = NULL;
            preOrderRes[i]->right = preOrderRes[i + 1];
        }
        //最后一个“表尾”需要封口
        preOrderRes[resSize - 1]->left = NULL;
        preOrderRes[resSize - 1]->right = NULL;
	}
};

方法二：使用非递归中序遍历的算法，将串接操作内置在中序遍历中。（时间复杂度O(n)，额外空间复杂度O(1)）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
	void flatten(TreeNode* root) {
		if (root == NULL) {
			return;
		}
		stack<TreeNode*> myStack;//辅助栈，由于中序遍历二叉树
        TreeNode* pre = root;//当前中序遍历完转换链表的表尾
		if (root->right != NULL) {//右子树不为空，保护现场
			myStack.push(root->right);
		}
		root = root->left;//转到左子树
		pre->left = NULL;//当前表尾left封口
		while (root != NULL || !myStack.empty()) {
			if (root != NULL) {
				if (root->right != NULL) {//右子树不为空，保护现场
					myStack.push(root->right);
				}
				pre->right = root;//当前根节点转移到转换后的表尾
				pre = pre->right;//后移表尾
				root = root->left;//转到左子树
				pre->left = NULL;//表尾left需要封口
			}
            else{
                root = myStack.top();//恢复现场
			    myStack.pop();
            }
		}
	}
};

方法三：展开一颗二叉树，先展开左子树、右子树，然后将右子树展开的结果接到左子树的展开结果的尾端即可。（时间复杂度O(n)，额外空间复杂度O(1)）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
	void flatten(TreeNode* root) {
        if (root == nullptr){
            return;
        }
        flatten(root->left);//先转换左子树
        flatten(root->right);//再转换右子树
        TreeNode* rNode = root->right;//标记右子树
        //再root->right定位到左子树转换后的链表的尾端
        root->right = root->left;
        root->left = nullptr;
        for (;root->right != nullptr;){
            root = root->right;
        }
        //再将root->right于尾端串接起来
        root->right = rNode;
	}
};