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

考察知识点： 树的中序遍历

题目分析：

 题目要求按照中序遍历的顺序将二叉树展开。对这样的问题都需要我们动手画图，观察规律。下图给出了某个二叉树的中序遍历。

 对该二叉树按照中序遍历的顺序展开之后，会形成如下图所示的链表：

 我们首先观察一个简单问题，对于该树的左子树，它发生了如下图所示的变化：

 发现该子树中，从根节点9指向左孩子3的指针改变成了从左孩子3指向根节点9。之后我们观察整棵子树：

 发现从根节点10指向左孩子9的指针改变成了从叶子节点6指向根节点10。说明我们应该根据中序遍历的顺序调整指针，需要找到从左孩子中不断向右查找，直到找到在左孩子中进行中序遍历访问到的最后一个节点，并将该节点的下一个节点设置为root。

 此外，我们还发现root指向右孩子的指针变成了root指向右孩子的叶子节点15。这个节点是在右子树中进行中序遍历访问到的第一个节点。

 现在，我们就能大致想到怎样解决这个问题了。通过找到左子树中进行中序遍历的最后一个节点和在右子树中进行中序遍历的第一个节点，修改这两个节点和root节点对应的指针，大致就能解决问题。

 但是，我们发现如果直接将root指针的下一个节点指向右子树中序遍历访问到的第一个节点，右子树的根节点就会丢失。这样自顶向下的修改方式是行不通的。我们可以通过自底向上的方法，先将左右子树展开成链表，最后再处理整个二叉树。

所用编程语言： C++

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    TreeNode* flattenII(TreeNode* root) {
        if (!root) return nullptr;
        //先将左右子树展开
        TreeNode *left = flattenII(root->left);
        TreeNode *right = flattenII(root->right);
        //如果有左子树的话，修改对应的指针
        if (left) {
            TreeNode *leftEnd = left;
            while (leftEnd->right) leftEnd = leftEnd->right;
            leftEnd->right = root;
        }
        root->right = right;
        root->left = nullptr;
        //如果有左子树的话链表的第一个节点是left,否则是根节点
        if (left) return left;
        else return root;
    }
};