LeetCode 226 Invert Binary Tree C++实现报错逻辑问题咨询

代码存在的核心问题 #

1. 递归调用错误：dfs2函数内部递归时错误调用了dfs1，而非自身。dfs1仅做中序遍历存值，不会执行赋值逻辑，导致除根节点外的所有节点值都没有被正确修改。
2. 实现思路不符合翻转二叉树的本质要求：你当前的思路是修改节点的值来模拟翻转效果，而翻转二叉树的标准定义是交换每个节点的左右子树指针，而非修改节点存储的数值。这种改值的方式仅能通过纯数值校验的测试用例，若节点存在其他自定义属性就会失效，且额外消耗了O(n)的存储空间存数值数组。

修正方案 #

方案1：修复你现有逻辑的错误 #

只需要把dfs2内的两个dfs1调用改为dfs2即可，修改后代码如下：

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;
        dfs2(root->right,vec,j);
        root->val=vec[j];
        j--;
        dfs2(root->left,vec,j);
    }
    
    TreeNode* invertTree(TreeNode* root) {
        vector<int> p;
        dfs1(root,p);
        int size=p.size()-1;
        dfs2(root,p,size);
        return root;        
    }
};

方案2：标准实现（交换左右子树，无额外存储开销，符合题意） #

不需要额外存储数值，直接递归交换每个节点的左右子节点即可：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return nullptr;
        // 交换当前节点的左右子树
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        // 递归处理左右子树
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

内容的提问来源于stack exchange，提问作者Newtan Ananda Gopal Mukhopadhy