Блог

Я работаю над проблемой 226 с кодом файла. Инвертировать двоичное дерево:

Учитывая root двоичное дерево, инвертируйте дерево и верните его корень.

Пример 1

 Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
 

Я написал следующий код на C , но он дает неправильный ответ. Я не знаю, есть ли недостаток в моей логике.

Код

 class Solution {
public:
    void dfs1(TreeNode* root,vector<int> amp;vec){
        if(root==NULL)
            return;
        dfs1(root->left,vec);
        vec.push_back(root->val);
        dfs1(root->right,vec);
    }

    void dfs2(TreeNode* root,vector<int> amp;vec,int amp;j) {
        if(root==NULL)
            return;
        dfs1(root->right,vec);
        root->val=vec[j];
        j--;
        dfs1(root->left,vec);
    }
    
    TreeNode* invertTree(TreeNode* root) {
        vector<int> p;
        dfs1(root,p);
        int size=p.size()-1;
        dfs2(root,p,size);
        return root;        
    }
};
 

Я просто выполняю обход по порядку и помещаю значения в вектор. Затем я снова выполняю обход по порядку, но на этот раз я иду другим путем, то есть справа налево.

Несколько проблем:

• В dfs2 вашем вызове dfs1 … это кажется не тем, что вы намеревались. Вы должны вызвать dfs2 и передать j в качестве третьего аргумента.
• Когда вы берете значения из конца vec и идете назад, вы не должны менять left местами и right , но все равно left сначала обрабатываете, а затем right
• Но теперь приходит главный удар: этот алгоритм никогда не отражает форму дерева, он просто заменяет значения в дереве. Таким образом, это может работать только в том случае, если форма входного дерева симметрична.

Из-за последнего пункта вам действительно нужно использовать другой алгоритм.

Я бы предложил алгоритм, который обходит узлы в любом порядке, который вы предпочитаете, и меняет left right местами значения и для каждого.

Я приведу здесь скрытое решение (спойлер) на случай, если вы не сможете заставить его работать:

TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;
invertTree(root->left);
invertTree(root->right);
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
return root;
}