内容：

大家好！今天，我要带大家走进一个有趣且实用的话题——如何用Java和C++将二叉树“拍扁”成链表。是不是觉得有点神秘？别急，我会详细解释，并给大家展示两种语言的实现方式。准备好了吗？让我们一起开启这场编程之旅吧！

什么是“拍扁”二叉树？

简单来说，就是把一棵二叉树按照前序遍历的顺序，变成一个“链表”。这个链表的特点是，每个节点的右指针指向下一个节点，而左指针全部为空。听起来是不是有点像把一棵树“压扁”成一条直线？

递归实现：Java vs C++

首先，我们来看看递归的实现方式。递归就像是你有一个任务，但你懒得自己做，于是你把它交给你的“小弟”去做，小弟也懒得做，又交给他的小弟……直到最后一个小弟终于完成了任务，然后一层层返回结果。

Java版本：

public void flatten(TreeNode root) {
    List<TreeNode> list = new ArrayList<>();
    preIterator(list, root);
    if (list.size() != 0 && list.size() >= 1) {
        for (int i = 1; i < list.size(); i++) {
            TreeNode pre = list.get(i - 1);
            TreeNode next = list.get(i);
            pre.left = null;
            pre.right = next;
        }
    }
}

public void preIterator(List<TreeNode> list, TreeNode root) {
    if (root == null) {
        return;
    }
    list.add(root);
    preIterator(list, root.left);
    preIterator(list, root.right);
}

C++版本：

void flatten(TreeNode* root) {
    vector<TreeNode*> vector;
    preIterator(vector, root);
    if (vector.size() <= 1) {
        return;
    }
    for (int i = 1; i < vector.size(); i++) {
        TreeNode* pre = vector.at(i - 1);
        TreeNode* next = vector.at(i);
        pre->left = nullptr;
        pre->right = next;
    }
}

void preIterator(vector<TreeNode*>& vector, TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    vector.push_back(root);
    preIterator(vector, root->left);
    preIterator(vector, root->right);
}

可以看到，Java和C++的实现几乎一模一样，只是语法上有些小差异。递归的核心思想就是：先把根节点加入列表，然后递归处理左子树，再递归处理右子树。最后，我们把列表中的节点一个个连接起来，形成一个链表。

迭代实现：Java vs C++

接下来，我们来看看迭代的实现方式。迭代就像是你自己亲自上阵，一步一步完成任务，没有“小弟”可以依赖。

Java版本：

public void flatten(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    List<TreeNode> list = new ArrayList<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            list.add(node);
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        node = node.right;
    }
    if (list.size() <= 1) {
        return;
    }
    for (int i = 1; i < list.size(); i++) {
        TreeNode pre = list.get(i - 1);
        TreeNode next = list.get(i);
        pre.left = null;
        pre.right = next;
    }
}

C++版本：

void flatten(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> stack;
    vector<TreeNode*> list;
    TreeNode* node = root;
    while (node != nullptr || !stack.empty()) {
        while (node != nullptr) {
            list.push_back(node);
            stack.push(node);
            node = node->left;
        }
        node = stack.top();
        stack.pop();
        node = node->right;
    }
    if (list.size() <= 1) {
        return;
    }
    for (int i = 1; i < list.size(); i++) {
        TreeNode* pre = list.at(i - 1);
        TreeNode* next = list.at(i);
        pre->left = nullptr;
        pre->right = next;
    }
}

迭代的实现方式稍微复杂一点，但思路也很清晰：我们用一个栈来模拟递归的过程，先把左子树的所有节点压入栈中，然后再处理右子树。最后，我们同样把列表中的节点连接成一个链表。

递归 vs 迭代：谁更胜一筹？

那么问题来了，递归和迭代，到底哪个更好呢？其实这就像是在问：你喜欢吃米饭还是面条？各有各的好处。

递归：代码简洁，容易理解，但可能会因为递归深度过大导致栈溢出。

迭代：效率更高，不会出现栈溢出的问题，但代码稍微复杂一些。

所以，选择哪种方式，取决于你的具体需求和场景。如果你喜欢简洁的代码，递归是个不错的选择；如果你追求效率，迭代可能更适合你。

为什么我们要坚持写代码？

最后，让我们聊聊为什么我们要坚持写代码。其实，写代码就像是在解谜题，每一次解决问题都是一种成就感。无论是递归还是迭代，都是我们解决问题的工具。每一次优化代码，每一次解决bug，都是我们成长的见证。

所以，无论你是选择递归还是迭代，重要的是你在这个过程中学到了什么，提升了什么。编程不仅仅是为了完成任务，更是为了让自己变得更好。

总结

今天我们通过Java和C++两种语言，分别用递归和迭代的方式实现了二叉树的“拍扁”操作。递归简洁易懂，迭代高效稳定，各有千秋。希望通过这篇文章，你能对这两种方法有更深的理解，也能在编程的道路上越走越远。

好了，今天的分享就到这里。如果你觉得这篇文章对你有帮助，别忘了点赞、分享，顺便关注我哦！我们下次再见！