Java教程

传入一个BST二分查找树,就可以将其转为双向链表,且返回链表头。牛客(Java)画图详解

本文主要是介绍传入一个BST二分查找树,就可以将其转为双向链表,且返回链表头。牛客(Java)画图详解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

传入一个BST二分查找树,就可以将其转为双向链表,且返回链表头
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

/**
 * 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
 */
public class ConvertTree2LinkedList {
    //传入一个BST二分查找树,就可以将其转为双向链表,且返回链表头
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null || pRootOfTree.left == null && pRootOfTree.right == null ){
            return pRootOfTree;
        }
        TreeNode left = Convert(pRootOfTree.left);
        TreeNode leftTail = left;
        while(leftTail != null && leftTail.right != null){
            leftTail = leftTail.right;
        }
        if(leftTail != null){
            //双向链表,左边指向left,右边指向right
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }
        TreeNode right = Convert(pRootOfTree.right);
        if(right != null){
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }
        return left == null ? pRootOfTree : left;
    }

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

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

在这里插入图片描述

这篇关于传入一个BST二分查找树,就可以将其转为双向链表,且返回链表头。牛客(Java)画图详解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!