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

考察知识点： 树的遍历

题目分析：

 题目要求按照先序遍历的顺序将二叉树展开成链表。首先我们要熟悉先序遍历，在先序遍历序列整体上，先遍历根节点，然后遍历左子树，最后再遍历右子树。

 可以看到在访问节点6之后就要开始遍历右子树了。可以直接将右子树连接到节点6的右子树上，因为这样不影响先序遍历的访问顺序，在对这一棵新树进行先序遍历与对原来的树进行先序遍历等价。

 将右子树移动到左子树末尾后就可以将根节点的right指针改为左子树，将left指针改为nullptr了。然后通过递归的方式，以root->right为根节点将子树的树形结构展开。

所用编程语言： 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* flattenTree(TreeNode* root) {
        // write code here
        if (!root) return nullptr;
        TreeNode *left = root->left;
        TreeNode *right = root->right;
        //当没有左子树时，如果有右子树，就要展开右子树
        if (!left) {
            if (right) flattenTree(right);
            return root;
        }
        //找到对左子树进行先序遍历的最后一个节点
        TreeNode *leftend = left;
        while (leftend->right) 
            leftend = leftend->right;
        //按照先序遍历的顺序，接下来要遍历右子树
        leftend->right = right;
        //按照题目要求展开成链表
        root->left = nullptr;
        root->right = left;
        //展开新的右子树
        flattenTree(root->right);
        return root;
    }
};