题目

分析

按要求转换二叉树；

分析转换要求，发现，新的二叉树是按照原二叉树的先序遍历结果构造的单支二叉树（只有右子树）。

发现规则，便容易处理了。得到先序遍历，构造即可。

AC代码

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    void flatten(TreeNode* root) {

        if (!root || (!root->left && !root->right))

            return;

        preTraverse(root);

        TreeNode *p = root;

        //节点个数

        int size = preT.size();

        for (int i = 1; i < size; ++i)

        {

            p->left = NULL;

            p->right = new TreeNode(preT[i]);

            p = p->right;

        }

    }

public:

    //先序遍历

    vector<int> preT;

    void preTraverse(TreeNode *root)

    {

        if (!root)

            return;

        preT.push_back(root->val);

        preTraverse(root->left);

        preTraverse(root->right);

    }

};

GitHub测试程序源码