题解 | #牛群的树形结构展开#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察了二叉树的展开，需要按照先序遍历的顺序将二叉树展开成一个单链表。

题目解答方法的文字分析

我们可以使用递归来解决这个问题。对于每一个节点，我们将它的左子树展开成一个链表，然后将它的右子树展开成一个链表，最后将左子树链表接在根节点的右子树上，然后将右子树链表接在左子树链表的末尾。这样就完成了二叉树的展开。

举个例子来帮助理解：

假设有以下二叉树：

     1
    / \
   2   5
  / \   \
 3   4   6

展开后的单链表应该是：1 -> 2 -> 3 -> 4 -> 5 -> 6

本题解析所用的编程语言

本题解析所用的编程语言是 C++。

完整且正确的编程代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    TreeNode* flattenTree(TreeNode* root) {
        if (!root) {
            return nullptr; // 如果当前节点为空，直接返回nullptr
        }
        
        TreeNode* leftFlat = flattenTree(root->left);   // 递归展开左子树
        TreeNode* rightFlat = flattenTree(root->right); // 递归展开右子树
        
        if (leftFlat) {
            root->right = leftFlat;  // 将左子树链表接在根节点的右子树上
            root->left = nullptr;     // 清空左子树
            while (leftFlat->right) {
                leftFlat = leftFlat->right; // 找到左子树链表的末尾节点
            }
            leftFlat->right = rightFlat; // 将右子树链表接在左子树链表的末尾
        } else {
            root->right = rightFlat; // 如果左子树为空，直接将右子树链表接在根节点的右子树上
            root->left = nullptr;    // 清空左子树
        }
        
        return root;
    }
};

在这段代码中，我们先递归展开左子树和右子树，然后根据左子树链表是否为空来连接节点。如果左子树链表不为空，我们将它连接到根节点的右子树上，并将右子树链表接在左子树链表的末尾。如果左子树链表为空，直接将右子树链表接在根节点的右子树上。

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！