题目描述

blablabla

样例

/**
 * 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:
    TreeNode* convert(TreeNode* root) {
        if (!root) return root;
        auto sides = dfs(root);
        return sides.first;
    }
    pair<TreeNode*, TreeNode*> dfs(TreeNode* root) {
        if (!root->left && !root->right) return {root, root};
        if (root->left && root->right) {
            auto lside =  dfs(root->left) , rside = dfs(root->right);
            lside.second->right =  root, root->left = lside.second;
            rside.first->left = root, root->right = rside.first;
            return {lside.first, rside.second};
        } 
        if (root->left) {
            auto lside =  dfs(root->left);
            lside.second->right =  root, root->left = lside.second;
            return {lside.first, root};
        }
        if (root->right) {

            auto rside = dfs(root->right);
            rside.first->left = root, root->right = rside.first;
            return {root, rside.second};

        }
    }
};

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla