109. 有序链表转换二叉搜索树 LeetCode

傷城~ 2022-12-04 14:58 115阅读 0赞

1.  将有序数组转换为二叉搜索树
2.  有序链表转换二叉搜索树

**题目说明**

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： \[-10, -3, 0, 5, 9\],

一个可能的答案是：\[0, -3, 9, -10, null, 5\], 它可以表示下面这个高度平衡二叉搜索树：

0
         / \
       -3   9
       /   /
     -10  5

**思路**  
先来看第108题，和109不同的是108输入的数据结构是数组。  
首先明确二叉搜索树的特性：

*  一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
 *  二叉树任意节点的左子树所有节点值都小于该节点的值，右子树所有节点值都大于该节点值

根据有序性和二叉树性质，可以使用找中间值然后二分数组，再在左右子数组进行递归地找中间值再二分数组，依次往下进行。。。

**代码**

/** * 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) { 
            TreeNode res=null;
            return toBST(nums,0,nums.length-1);
        }
        TreeNode toBST(int[] nums,int i,int j)
        { 
            if(i>j)return null;
           
               int mid=(i+j)/2;	//或者 i+(j-i)/2
               TreeNode root=new TreeNode(nums[mid]);
               root.left=toBST(nums,i,mid-1);
               root.right=toBST(nums,mid+1,j);
           
            return root;
        }
    }

第109题把有序数组换成了链表，总体的思路还是不变，但要去找链表的中间值，需要采用双指针来做，即快慢指针，快指针走两步，慢指针走一步，当快指针走完全部链表节点，慢指针停留在中间节点，获取慢指针即可

**代码**

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
    /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
    class Solution { 
        public TreeNode sortedListToBST(ListNode head) { 
            return buildTree(head,null);
        }
        
        TreeNode buildTree(ListNode left,ListNode right){ 
            if(left==right){ 
                return null;
            }
            
            ListNode mid = getMidNode(left,right);
            TreeNode root = new TreeNode(mid.val);
            root.left = buildTree(left,mid);
            root.right = buildTree(mid.next,right);
            return root;
            
        }
                      
        //获取中间节点的函数，在第一次调用时，可以让结束节点为null 
        ListNode getMidNode(ListNode left,ListNode right){ 
            ListNode fast = left;
            ListNode slow = left;
            
            while(fast!=right&&fast.next!=right){ 
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
    }