108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

問題描述

將一個按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹。一個高度平衡二叉樹是指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1。

解題思路

遞歸思路。選取升序排列數(shù)組里的中間值作為根節(jié)點，然后分別用medium的前/后半部分作為參數(shù)遞歸構(gòu)建左/右子樹。（如果元素個數(shù)為偶數(shù)時，那么選擇右邊的那個數(shù)作為中間值）

代碼實現(xiàn)

/**
 * 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 sortedArrayToBST(int[] nums) {
        int len = nums.length;
        if(len == 0){
            return null;
        }
        int mediumIndex = len/2;
        TreeNode root = new TreeNode(nums[mediumIndex]);

        //構(gòu)建左子樹
        if(mediumIndex == 0){
            root.left = null;
        }else{
            int[] left = new int[mediumIndex];
            for(int i = 0; i < mediumIndex; i++){
                left[i] = nums[i];
            }
            root.left = sortedArrayToBST(left);
        }

        //構(gòu)建右子樹
        if(mediumIndex == len - 1){
            root.right =null;
        }else{
            int[] right = new int[len - mediumIndex - 1];
            for(int i = 0; i < len - mediumIndex - 1; i++){
                right[i] = nums[i + mediumIndex + 1];
            }
            root.right = sortedArrayToBST(right);
        }

        return root;
    }
}

109. 有序鏈表轉(zhuǎn)換二叉搜索樹

問題描述

給定一個單鏈表，其中的元素按升序排序，將其轉(zhuǎn)換為高度平衡的二叉搜索樹。
本題中，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1。

解題思路

基本思路與上一題相同，采用快慢指針找到升序鏈表的中間節(jié)點。

代碼實現(xiàn)

/**
 * 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) {
        if(head == null){
            return null;
        }
        ListNode slow = head, fast = head;
        // 開辟新的空間存儲左子樹節(jié)點
        ListNode left = new ListNode(0);
        ListNode leftHead = left;
        //先遍歷找到鏈表的中間節(jié)點
        while(fast != null && fast.next != null){
            left.next = new ListNode(slow.val);
            left = left.next;
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(leftHead.next);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}