二叉搜索树与双向链表
二叉搜索树与双向链表
题目
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路
举例说明：
二叉搜索树如上图所示，我们将其转换为配需双向链表。
根据二叉搜索树的特点：左结点的值<根结点的值<右结点的值，我们不难发现，使用二叉树的中序遍历出来的数据的数序，就是排序的顺序。因此，首先，确定了二叉搜索树的遍历方法。
接下来，我们看下图，我们可以把树分成三个部分：值为10的结点、根结点为6的左子树、根结点为14的右子树。根据排序双向链表的定义，值为10的结点将和它的左子树的最大一个结点链接起来，同时它还将和右子树最小的结点链接起来。
按照中序遍历的顺序，当我们遍历到根结点时，它的左子树已经转换成一个排序的好的双向链表了，并且处在链表中最后一个的结点是当前值最大的结点。我们把值为8的结点和根结点链接起来，10就成了最后一个结点，接着我们就去遍历右子树，并把根结点和右子树中最小的结点链接起来。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode temp =null;
TreeNode head =null;
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return null;
}
helper(pRootOfTree);
return temp;
}
public void helper(TreeNode root){
if(root == null){
return;
}
helper(root.left);
if(head == null){
head = root;
temp = root;
}else{
head.right = root;
//根是左子树的右边
root.left = head;
//根的左边是右子树
head = root;
}
helper(root.right);
}
}
主函数 打印函数
public static void main(String[] args) {
TreeNode node10 = new TreeNode(10);
TreeNode node6 = new TreeNode(6);
TreeNode node14 = new TreeNode(14);
TreeNode node4 = new TreeNode(4);
TreeNode node8 = new TreeNode(8);
TreeNode node12 = new TreeNode(12);
TreeNode node16 = new TreeNode(16);
node10.left = node6;
node10.right = node14;
node6.left = node4;
node6.right = node8;
node14.left = node12;
node14.right = node16;
System.out.println("改变前");
printTree(node10);
System.out.println();
System.out.println("=========================");
System.out.println("改变后");
printList(Convert(node10));
}
private static void printTree(TreeNode root) {
if (root != null) {
printTree(root.left);
System.out.print(root.val + "->");
printTree(root.right);
}
}
private static void printList(TreeNode head) {
while (head != null) {
System.out.print(head.val + "->");
head = head.right;
}
System.out.println("null");
}
代码一(递归)
public static TreeNode Convert(TreeNode root) {
if(root == null){
return null;
}
if(root.left==null&&root.right==null)
{
return root;
}
// 1.将左子树构造成双链表，并返回链表头节点
TreeNode left = Convert(root.left);
TreeNode p = left;
// 2.定位至左子树双链表最后一个节点
while(p!=null&&p.right!=null){
p = p.right;
}
// 3.如果左子树链表不为空的话，将当前root追加到左子树链表
if(left!=null){
p.right = root;
root.left = p;
}
// 4.将右子树构造成双链表，并返回链表头节点
TreeNode right = Convert(root.right);
// 5.如果右子树链表不为空的话，将该链表追加到root节点之后
if(right!=null){
right.left = root;
root.right = right;
}
return left!=null?left:root;
}
代码二（递归）
抓住二叉搜索树的本质，可以使用中序遍历进行排序。将左子树构造成双链表，然后再递归右子树。注意：递归时一定要判断当前结点是否为null。
public class Solution {
TreeNode head = null;
TreeNode returnhead = null;
public TreeNode Convert(TreeNode pRootOfTree) {
PostOrder(pRootOfTree);
return returnhead;
}
public void PostOrder(TreeNode root){
if(root==null) return;
PostOrder(root.left);
if(head==null){
head = root;
returnhead = root;
}else{
head.right = root;
root.left = head;
head = root;
}
PostOrder(root.right);
}
}
代码三（非递归）利用栈
如果不使用递归，可以使用堆栈来保存之前的节点，核心思想还是使用中序遍历，但是使用堆栈编写代码较为繁琐，没有递归简洁。
import java.util.Stack;
public class Solution {
public TreeNode ConvertBSTToBiList(TreeNode root) {
if(root==null)
return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
TreeNode pre = null; // 用于保存中序遍历序列的上一节点
boolean isFirst = true;
while(p!=null||!stack.isEmpty()){
while(p!=null){
stack.push(p);
p = p.left;
}
p = stack.pop();
if(isFirst){
root = p; // 将中序遍历序列中的第一个节点记为root
pre = root;
isFirst = false;
}else{
pre.right = p;
p.left = pre;
pre = p;
}
p = p.right;
}
return root;
}
}
代码四 利用栈 非递归
public static TreeNode convert(TreeNode root){
if(root == null){
return null;
}
TreeNode list = null;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()){
if(root!=null){
stack.push(root);
root = root.right;
}else{
root = stack.pop();
if(list == null){
list = root;
}else{
list.left = root;
root.right = list;
list = root;
}
root = root.left;
}
}
return list;
将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST(nums,0,nums.length-1);
}
public TreeNode sortedArrayToBST(int [] nums,int left,int right){
if(left>right){
return null;
}
//边界条件，注意是left>right
int mid=(left+right)/2;
TreeNode root=new TreeNode(nums[mid]);
root.left=sortedArrayToBST(nums,left,mid-1);
//递归向左探索，范围变成left~mid-1;
root.right=sortedArrayToBST(nums,mid+1,right);
return root;
}
}
有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
return helper(head, null);
}
private TreeNode helper(ListNode head, ListNode tail) {
if (head == tail) return null;
// mid
ListNode slow = head;
ListNode fast = head;
while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = helper(head, slow);
root.right = helper(slow.next, tail);
return root;
}
}
京公网安备 11010502036488号