剑指Offer-二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

思路

思路一:

  1. 由于要求链表是有序的,可以借助二叉树中序遍历,因为中序遍历算法的特点就是从小到大访问结点。中序遍历过程中,根节点不断加到右边,这样可以保持从左到右升序。
  2. 由于中序遍历过程正好是转换成链表的过程,即可采用递归处理。

代码实现

package Tree;

/**
 * 二叉搜索树与双向链表
 * 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
 */
public class Solution38 {
    //双向链表的左边头结点和右边头节点
    TreeNode leftHead = null;
    TreeNode rightHead = null;

    /**
     * 中序遍历,递归
     *
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        //递归调用叶子节点的左右节点返回null
        if (pRootOfTree == null) return null;
        //第一次运行时,它会使最左边叶子节点为链表第一个节点
        Convert(pRootOfTree.left);
        if (rightHead == null) {
            leftHead = rightHead = pRootOfTree;
        } else {
            //把根节点插入到双向链表右边,rightHead向后移动
            rightHead.right = pRootOfTree;
            pRootOfTree.left = rightHead;
            rightHead = pRootOfTree;
        }
        //把右叶子节点也插入到双向链表(rightHead已确定,直接插入)
        Convert(pRootOfTree.right);
        //返回左边头结点
        return leftHead;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习和数学

[算法与数据结构] 《算法导论》堆排序笔记

堆排序的实现是靠叫做“堆”的数据结构来实现的。所以学习堆排序,首先要了解什么是堆 堆 堆是一个数组,每个结点表示数组中的一个元素,堆可以看做是一个近似的完全二叉...

32690
来自专栏java系列博客

Iterator在ArrayList中的源码实现

21620
来自专栏java小白

ArrayList源码详解

18450
来自专栏nnngu

数据结构07 二叉树

这篇文章开始总结 树和二叉树。 什么是树呢? 1、树的定义 (1)有且仅有一个特定的称为根(root) 的节点。 (2)当 n>1 时,其余节点可分为 m(m>...

37140
来自专栏Java后端技术

一道面试题引发的思考

为什么呢?那么我们怎么来发现它背后的秘密呢?答案只有一个:那就是通过源码来解惑(ArrayList部分源码)。

7600
来自专栏Bingo的深度学习杂货店

Q108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

33230
来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

10620
来自专栏java技术学习之道

Java进阶--深入理解ArrayList实现原理

13230
来自专栏余林丰

有关ArrayList常用方法的源码解析

jdk1.7.0_79   我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问...

23870
来自专栏俞其荣的博客

ArrayList内部原理解析Header源码分析Footer

28580

扫码关注云+社区

领取腾讯云代金券