开发者社区> 问答> 正文

关于最近比较火的二叉树翻转的问题

这是我想当然写的代码,实际发现根本不行(在在新问答提交居然测试通过了,但是本地跑测试不行,难道是我 main 函数里面初始做得不对?).

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* invertTree(struct TreeNode* node){
    if(node == NULL){
        return node;
    }
    struct TreeNode* tmp = node->left;
    node->left = invertTree(node->right);
    node->right = invertTree(tmp);
    return node;
}
int main(){
    //        4
    //      /   \
    //     2     7
    //    / \   / \
    //   1   3 6   9

    struct TreeNode rootNode;
    struct TreeNode leftNode;
    struct TreeNode rightNode;

    struct TreeNode leftNode1;
    struct TreeNode leftNode2;

    struct TreeNode rightNode1;
    struct TreeNode rightNode2;


    leftNode1.val = 1;
    leftNode1.left = NULL;
    leftNode1.right = NULL;

    leftNode2.val = 3;
    leftNode2.left = NULL;
    leftNode2.right = NULL;

    leftNode.val = 2;
    leftNode.left = &leftNode1;
    leftNode.right = &leftNode2;

    rightNode1.val = 6;
    rightNode1.left = NULL;
    rightNode1.right = NULL;

    rightNode2.val = 9;
    rightNode2.left = NULL;
    rightNode2.right = NULL;

    rightNode.val = 7;
    rightNode2.left = &rightNode1;
    rightNode2.right = &rightNode2;

    rootNode.val = 4;
    rootNode.left = &leftNode;
    rootNode.right = &rightNode;

    invertTree(&rootNode);
}

编译能通过,执行就提示Segmentation fault: 11

展开
收起
a123456678 2016-06-08 14:25:47 2076 0
1 条回答
写回答
取消 提交回答
  • 码农|Coder| Pythonista

    思路是对的,其实可以更简单,看下面的代码:

    struct NormalNode { 
    int value; 
    struct NormalNode *left; 
    struct NormalNode *right; 
    }; 
    
    struct ReversedNode { 
    int value; 
    struct ReversedNode *right; 
    struct ReversedNode *left; 
    }; 
    
    struct ReversedNode *reverseTree(struct NormalNode *root) { 
    return (struct ReversedNode *)root; 
    } 

    1)你的用于反转的递归方法没有判断结束条件
    2)指针需要初始化,修改成这样:

    struct TreeNode* node2;
    node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));

    3) 我将你的算法提交到leecode显示是通过的,我想是创建二叉树时出了问题
    我将你的代码调试了一下,发现是这个问题

    rightNode.val = 7;
    rightNode.left = &rightNode1;
    rightNode.right = &rightNode2;
    2019-07-17 19:31:54
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载