vue VMware highcharts scrapy vue绑定事件 react脚手架搭建 php零基础入门视频 jquery遍历子元素 jq获取最后一个子元素 android逆向工程师 mysql升序 docker查看所有容器 mysql自然连接 python学习 python自学教程 python写入文件 javaif语句 java接口怎么写 linux下载安装 php实例 数据库系统概论第五版 联发科p70 pdf拆分工具 电脑密码查看器 begininvoke 自动回复机器人 js保留两位小数 电脑待机费电吗 暗黑3挂机plusready 微信昵称特殊字符保存 ps祛痘 淘新闻下载 su镜像 街机roms下载 centos配置ip 聊呗电脑版 ps透明度 饥荒海难最变态的人物 js数组排序 屏幕录像工具
当前位置: 首页 > 学习教程  > 编程语言

剑指offer66二叉搜索树和双向链表

2021/1/28 22:43:46 文章标签:

二叉搜索树和双向链表问题描述分析AC代码问题描述 问题链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/ 分析 题目虽然短短的两行字,但真心不简单(哭)。这道题的关键是二叉搜索树树…

二叉搜索树和双向链表

  • 问题描述
  • 分析
  • AC代码

问题描述

在这里插入图片描述
问题链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

分析

题目虽然短短的两行字,但真心不简单(哭)。这道题的关键是二叉搜索树树的中序遍历
首先什么是二叉搜索树呢?就是根的左子树的值全部小于根节点的值,根的右子树的值全部大于根节点的值(递归下去,其左子树与右子树也满足该性质)巧的是二叉搜索树的中序遍历是递增的,刚好满足题目的排序要求(这就很棒)。

解题三部曲 先排序,再双向链表,最后循环。

  1. 排序: 节点应从小到大排序,用中序遍历即可解决
  2. 双向链表:(将left当做前驱,right当做后继) 在构建相邻节点(设前驱节点 prev,当前节点 cur (两个千万别冲突prev和cur是我们创建的用来方便连接的)关系时,不仅应 pre.right = cur ,也应 cur.left = pre

结合下面图片来理解
最开始
在这里插入图片描述
更新第一个前驱
在这里插入图片描述
更新第一个后继
在这里插入图片描述
3. 循环链表: 设链表头节点 head 和尾节点 tail ,则应构建 head.left = tailtail.right = head

AC代码

class Solution {
    public Node prev=null;
    //中序遍历排序 并连接双向链表
    public  void inOrder(Node cur)
    {
        if(cur==null) return ;
            inOrder(cur.left);
            cur.left=prev;
            if(prev!=null)
            {
                prev.right=cur;
            }
            prev=cur;
            inOrder(cur.right);
        }
    
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        inOrder(root);
        Node head=root;
        Node tail=root;
        //找头
        while(head.left!=null)
        {
            head=head.left;
        }
        //找尾
        while(tail.right!=null)
        {
            tail=tail.right;
        }
        //连接头和尾
        head.left=tail;
        tail.right=head;
        return head;
    }
}

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

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?