本文共 1200 字,大约阅读时间需要 4 分钟。
题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。Java
/*// Definition for a Node.class Node { public int val; public Node left; public Node right; public Node() {} public Node(int _val) { val = _val; } public Node(int _val,Node _left,Node _right) { val = _val; left = _left; right = _right; }};*/class Solution { public Node head=null; public Node tail=null; public Node treeToDoublyList(Node root) { if(root==null) return null; //构建双向链表 build(root); //构建双向循环链表 head.left=tail; tail.right=head; return head; } public void build(Node root){ if(root==null) return; build(root.left); if(head==null){ head=tail=root; } else{ tail.right=root; root.left=tail; tail=root; //把根节点加入到左边的双向链表中 } build(root.right); }}