怎么将二叉树变为树
二叉树是一种树形结构，在实际应用中，我们有时候会需要将二叉树变为树。那么，如何将一个二叉树转为一棵普通的树呢？本篇文章将从多个角度进行分析。
一、二叉树和树的区别
二叉树是一种特殊的树形结构，每个节点最多有两个子节点。相比较而言，一棵树可以有多个子节点。因此，我们需要将二叉树转为树时，需要将每个二叉树节点的左右子节点合并在一起，形成一个多叉树。
二、二叉树转树的方法
1.递归法
递归是二叉树转为树的主要方法之一。对于二叉树的每个节点，我们可以先将其左右子节点合并为一个链表，然后将该链表和当前节点作为参数，递归调用函数，直至转换完成。该方法的时间复杂度为O(n)，其中n是树的节点数。
2.迭代法
迭代法是另一种将二叉树转为树的方法。对于二叉树的每个节点，我们可以利用栈来将其左右子节点压入栈中，并将右子节点的指针设为空。然后，我们可以不断弹出栈顶元素，将其左子节点和右子节点“接到”链表中，直至转换完成。该方法的时间复杂度也为O(n)，其中n是树的节点数。
三、二叉树到树的实现
下面我们来看看，如何将上述方法具体实现。首先，我们需要定义一个节点结构体，如下所示：
```c++
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
接下来，我们可以先定义一个Stack，将根节点入栈。然后，我们可以不断弹出Stack的栈顶元素，将其左右子节点合并为一个链表，并将该链表和当前节点作为参数，递归调用函数。最后得到一棵普通的树。
```c++
class Solution
{
public:
TreeNode* flatten(TreeNode* root)
{
if (!root)
return NULL;
stack
TreeNode* pre = new TreeNode(-1); // 定义虚拟头节点
TreeNode* res = pre; // 保留头节点
while (!s.empty())
{
auto t = s.top();
s.pop(); // 取栈顶
if (t->right)
s.push(t->right);
if (t->left)
s.push(t->left); // 先右再左，保证链表顺序正确
pre->right = t; // 链接链表
pre->left = NULL;
pre = t; // 更新pre节点
}
return res->right;
}
};
```
最后，我们可以利用上述函数将一棵二叉树转换成一棵普通的树。如下所示：
```c++
int main()
{
TreeNode root(1);
TreeNode c2(2);
TreeNode c5(5);
TreeNode c3(3);
TreeNode c4(4);
TreeNode c6(6);
root.left = &c2;
root.right = &c5;
c2.left = &c3;
c2.right = &c4;
c5.right = &c6;
Solution s;
s.flatten(&root);
return 0;
}
```
四、文章
