题解 | #牛群的树形结构展开II# 中序遍历

知识点

中序遍历

思路

先中序遍历获取到指针的先后顺序，之后重新建立指针间的关系。

时间复杂度

每个节点访问常数次，

AC code（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类
     */
    vector<TreeNode*> v;
    TreeNode* flattenII(TreeNode* root) {
        if (!root) return root;
        dfs(root);
        int n = v.size();
        for (int i = 1; i < n; i ++) {
            v[i - 1]->right = v[i];
            v[i - 1]->left = nullptr;
        }
        v.back()->left = v.back()->right = nullptr;
        return v[0];
    }
    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->left);
        v.push_back(root);
        dfs(root->right);
    }
};