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

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

题目考察的知识点

这道题目考察了二叉树的中序遍历和链表操作。需要将一个二叉树按照中序遍历的顺序展开成一个链表，其中左子树为空，右子树指向链表中的后一个节点。

题目解答方法的文字分析

解决这道题的关键在于中序遍历二叉树，同时将遍历的节点按照顺序串联起来，形成一个链表。

1. 首先，我们创建一个哑节点作为链表的起始点，并创建一个指针 prev 指向这个哑节点。这样我们就能在遍历过程中不断地将节点接在 prev 的后面。
2. 使用中序遍历的方式遍历二叉树。对于每个节点，先递归处理左子树，然后将当前节点接在 prev 的右侧，左子树置为空，更新 prev 为当前节点，最后递归处理右子树。
3. 最后，返回哑节点的右子树，即为展开后的链表。

思路示例：

考虑以下二叉树：

     4
    / \
   2   6
  / \   \
 1   3   5

我们按照中序遍历的顺序展开，得到链表：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* flattenII(TreeNode* root) {
        if (!root) {
            return nullptr;
        }
        
        TreeNode* dummy = new TreeNode(-1); // 创建一个哑节点作为链表的起始点
        TreeNode* prev = dummy;
        
        inorderFlatten(root, prev); // 中序遍历展开二叉树
        
        TreeNode* flattened = dummy->right;
        delete dummy; // 删除哑节点
        
        return flattened;
    }
    
    void inorderFlatten(TreeNode* node, TreeNode*& prev) {
        if (!node) {
            return;
        }
        
        inorderFlatten(node->left, prev); // 递归展开左子树
        
        prev->right = node; // 当前节点接在前一个节点的右侧
        prev->left = nullptr; // 左子树置为空
        
        prev = node; // 更新前一个节点为当前节点
        
        inorderFlatten(node->right, prev); // 递归展开右子树
    }
};

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