[剑指offer] 二叉搜索树与双向链表

题目描述

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

解题思路

题目可能比较难理解,可以看如下的图,我们有一棵二叉搜索树,要求得右边的双向链表。

在二叉搜索树中,左子结点的值总是小于父结点的值,右子节点的值总是大于父结点的值。因此我们在转换成排序双向链表时,原先指向左子结点的指针调整为链表中指向前一个结点的指针,原先指向右子节点的指针调整为链表中指向后一个结点的指针。 因为中序遍历是按照从小到大的顺序遍历二叉搜索树,所以我们用中序遍历树中的每一个节点得到的正好是要求的排好序的。遍历过程如下: 每次遍历节点的左孩子、右孩子,把左孩子指向转换链表的尾节点,并把末尾指针的右孩子指向自己。右孩子指向节点的右孩子。如果没有右孩子就返回。这一过程可以用递归实现。

参考代码

递归解法
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    TreeNode head = null;
    TreeNode end = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        ConvertSub(pRootOfTree);
        return head;
    }
    public void ConvertSub(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            return ;
        Convert(pRootOfTree.left);
        if(end == null){
            head = pRootOfTree;
            end = pRootOfTree;
        }else{
            end.right = pRootOfTree;
            pRootOfTree.left = end;
            end = pRootOfTree;
        }
        Convert(pRootOfTree.right);
    }
}
非递归解法
import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        TreeNode head = null;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>();
        while(pRootOfTree != null || !stack.isEmpty()){
            while(pRootOfTree != null){
                stack.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }
            pRootOfTree = stack.pop();
            if(head == null){
                head = pRootOfTree;
                pre = pRootOfTree;
            }else{
                pre.right = pRootOfTree;
                pRootOfTree.left = pre;
                pre = pRootOfTree;
            }
            pRootOfTree = pRootOfTree.right;
        }
        return head;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏好好学java的技术栈

“365算法每日学计划”:06打卡-单向循环链表

单向循环链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。

8110
来自专栏LeetCode

LeetCode 102 & 103 &107 & 637. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie,...

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

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

13230
来自专栏nnngu

数据结构07 二叉树

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

37040
来自专栏武培轩的专栏

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

题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路 思路一: 由于要求链表是有序...

34530
来自专栏积累沉淀

JDK源码分析-ArrayList分析

花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess,...

18950
来自专栏闻道于事

Java常用工具类之时间转换

import java.text.DecimalFormat; import java.text.ParseException; import java...

35260
来自专栏desperate633

ArrayList实现原理分析(Java源码剖析)ArrayList使用的存储的数据结构ArrayList的初始化ArrayList是如何动态增长ArrayList如何实现元素的移除ArrayList

ArrayList是我们经常使用的一个数据结构,我们通常把其用作一个可变长度的动态数组使用,大部分时候,可以替代数组的作用,我们不用事先设定ArrayList的...

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

Q100 Same Tree

Given two binary trees, write a function to check if they are the same or not. T...

33660
来自专栏武培轩的专栏

剑指Offer-从上往下打印二叉树

题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 思路 使用两个队列一个存放节点,一个存放值。先将根节点加入到队列中,然后遍历队列中的元素,遍历...

28870

扫码关注云+社区

领取腾讯云代金券