一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 355|回复: 1
收起左侧

[Leetcode] Convert Sorted List to Binary Search Tree 求答疑

[复制链接] |试试Instant~ |关注本帖
pan_y 发表于 2015-3-21 09:13:26 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
     TreeNode *sortedListToBST(ListNode *head) {
        int n = 0;
        ListNode * p = head;
        while(p!=NULL){
            n++;
            p = p->next;
        }
        return sortedListToBST(head,0,n-1);
    }
   
private:
    TreeNode * sortedListToBST(ListNode * list, int start, int end){
        if(start>end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode* leftChild = sortedListToBST(list,start,mid -1);
        TreeNode* parent = new TreeNode(list->val);
        parent->left = leftChild;
        list = list->next;  // this is wrong, because the update of list in the lower level is invisible to the upper level
        parent->right = sortedListToBST(list, mid +1, end);
        return parent;
    }
};

上面的代码有bug,而如果把list设成全局的变量就解决问题了,正确代码如下:
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
        int n = 0;
        ListNode * p = head;
        while(p!=NULL){
            n++;
            p = p->next;
        }
        list = head;
        return sortedListToBST(0,n-1);
    }
   
private:
    ListNode * list;
    TreeNode * sortedListToBST( int start, int end){
        if(start>end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode* leftChild = sortedListToBST(start,mid-1);
        TreeNode* parent = new TreeNode(list->val);
        parent->left = leftChild;
        list = list->next;
        parent->right = sortedListToBST(mid+1,end);
        return parent;
    }
};
求解释;自己觉得大概是:the update of list in the lower level is invisible to the upper level,since the update of list is stored in the stack. 但不是很清楚
stellari 发表于 2015-3-21 23:16:10 | 显示全部楼层
list是个局部变量,它在进入函数时被创建,离开函数时被清除。它不过是上层传来的某个参数的一个副本而已。所以当然不会够影响到上级函数中的任何变量,包括上级函数中的同名变量list。至于你说的update ... is stored in the stack,这是实际情况,但是我认最好能强调一下list是在栈上创建的“副本”这件事,否则这个解释听起来就稍显不够清晰。
回复 支持 1 反对 0

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 01:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表