Invert Binary Tree in C++

Question

I am working on LeetCode problem 226. Invert Binary Tree:

Given the root of a binary tree, invert the tree, and return its root.

Example 1

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

I wrote the following C++ code, but it gives the wrong answer. I don't know whether there is a flaw in my logic.

Code

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

    void dfs2(TreeNode* root,vector<int> &vec,int &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;        
    }
};

I am just doing an inorder traversal and pushing the values into a vector. Then again I perform an inorder traversal, but this time I am traversing the other way, that is from right to left.

Answer 1

Several issues:

• In dfs2 you call dfs1... that seems not what you intended. You should call dfs2, and pass j as third argument.

• As you take values from the end of vec and walk backwards, you should not swap left and right, but still process left first, and then right

• But now comes the major blow: this algorithm never mirrors the shape of the tree, it merely replaces the values in the tree. So this can only work if the shape of the input tree is symmetric.

Because of the latter point you really need to use a different algorithm.

I would suggest an algorithm which traverses the nodes in any order you prefer, and swap the left and right values for each.

I'll provide here a hidden solution (spoiler) in case you cannot make it work:

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;
}