Python 微信小程序 Wendy 作用域 centos7 xamarin charts configuration coldfusion web前端开发实战项目 spark文档 cos图像和sin图像 mser算法 字符串中包含某个字符串 二分查找python pythonfor循环 python环境安装教程 java集合 javasocket通信 java的集合框架 java文档 java新建文件 java输出当前时间 java字符串格式化 java中string的方法 php开发实例 php入门例子 易语言进度条 脚本软件 图片生成网址 backtrack3 识别音乐的软件 博途v14安装教程 list删除指定元素 js验证码 骰子牛牛怎么玩 python求和 驱动精灵绿色版 抽出滤镜下载 php定时任务
当前位置: 首页 > 学习教程  > 编程语言

链表 leetcode 109. 有序链表转换二叉搜索树

2021/2/13 18:21:16 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目内容 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表: [-10, -3, 0, 5, 9],…

题目内容

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表: [-10, -3, 0, 5, 9],

一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

  0
 / \

-3 9
/ /
-10 5

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表: [-10, -3, 0, 5, 9],

一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

  0
 / \

-3 9
/ /
-10 5

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表: [-10, -3, 0, 5, 9],

一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

  0
 / \

-3 9
/ /
-10 5

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree

c语言解答

 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* sortedListToBST(struct ListNode* head){
    //链表是排好序的,所以直接用快慢指针找到中间的结点,快指针速度是慢指针两倍
    //考虑树是空的时候
    if(head==NULL)
        return NULL;
    //考虑树中只有一个节点的时候,没有这个时候会一直递归下去,这也是终止条件
    if(head->next==NULL){
        struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val=head->val;
        root->left=NULL;
        root->right=NULL;
        return root;
    }
    //定义快慢指针
    struct ListNode *slow=head;
    struct ListNode *fast=head;
    //用指针p,让他表示slows前面那个指针,这样在递归时候可以把树折成两部分
    struct ListNode*p=head;
    //while循环完后的slow就在链表中间,快慢指针
    while(fast!=NULL&&fast->next!=NULL){
        p=slow;
        slow=slow->next;
        fast=fast->next->next;
    }
    //将树分成两部分
    p->next=NULL;
    //动态申请树,让他足有量变指向下一个root
    //动态申请后,一定要为其初始化
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=slow->val;
    //递归
    root->left=sortedListToBST(head);
    root->right=sortedListToBST(slow->next);
    return root;
}

java解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        //链表是排好序的,所以直接用快慢指针找到中间的结点,快指针速度是慢指针两倍
        //考虑树是空的时候
        if(head==null)
            return null;
        //考虑树中只有一个节点的时候,没有这个时候会一直递归下去,这也是终止条件
        if(head.next==null)
            return new TreeNode(head.val);
        //定义快慢指针
        ListNode slow=head;
        ListNode fast=head;
        //用指针p,让他表示slows前面那个指针,这样在递归时候可以把树折成两部分
        ListNode p =head;
        //while循环完后的slow就在链表中间,快慢指针
        while(fast!=null&&fast.next!=null){
            p=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        //将树分成两部分
        p.next=null;
        //java中申请可以直接赋值,没有赋值的赋成默认值
        TreeNode root=new TreeNode(slow.val);
        //递归
        root.left=sortedListToBST(head);
        root.right=sortedListToBST(slow.next);
        return root;
    }
}

总结

递归注意终止条件,c语言动态申请记得初始化.java会赋默认值. 快慢指针 递归


本文链接: http://www.dtmao.cc/news_show_700246.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?