题解 | 二叉树的镜像|注意递归不要对原始数据造成破坏!

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if (pRoot == nullptr)
            return nullptr;

        TreeNode* left = Mirror(pRoot->left);
        TreeNode* right = Mirror(pRoot->right);
       
        pRoot->left = right;
        pRoot->right = left;
        // pRoot->left = Mirror(pRoot->right);
        // pRoot->right = Mirror(pRoot->left);

        return pRoot;
    }
};

28,29行的经典错误,这个在递归的时候修改了原本的tree。在递归的时候应该避免这种问题,应该把我需要做的递归在新的变量中保存起来然后去做执行。

树结构示例:

假设我们有如下的树:

    1
   / \
  2   3

递归步骤详解

  1. 初始调用 Mirror(pRoot),pRoot 为根节点 1。首先执行 pRoot->left = Mirror(pRoot->right),递归处理右子树(节点 3)。
  2. 进入右子树的递归调用 Mirror(pRoot->right),pRoot 为节点 3。节点 3 没有子节点,因此直接返回 3。
  3. 返回到根节点 1 的第一个递归调用,完成 pRoot->left = Mirror(pRoot->right)。此时根节点的左子树已经被设置为节点 3。树结构此时为:
  4. 开始执行第二个递归调用 pRoot->right = Mirror(pRoot->left),递归处理左子树(注意:此时的 pRoot->left 是刚刚设置为的节点 3)。
  5. 进入左子树的递归调用 Mirror(pRoot->left),pRoot 为节点 3。同样,节点 3 没有子节点,因此直接返回 3。
  6. 返回到根节点 1,完成 pRoot->right = Mirror(pRoot->left)。此时根节点的右子树也被设置为节点 3。树结构此时为:
  1
 / \
3   3

这个就是属于由于调用顺序的问题加上直接在原来的数据上做了修改,导致后面的数据的操作鲁棒性不够强。建议的就是像这里一样直接在栈上新创建变量来做递归,确保不受运行先后顺序影响。#剑指offer#

全部评论

相关推荐

不愿透露姓名的神秘牛友
06-29 17:30
找实习找着找着就要进入7月了,马上秋招也要开始了,找实习还有意义吗?
绝迹的星:有面就面, 没面上就当日薪4位数大佬免费培训, 面上了再考虑要不要实习
点赞 评论 收藏
分享
牛客92804383...:在他心里你已经是他的员工了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务