首页 > 代码库 > Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

2024-08-10 06:58:47   219人阅读

Convert Sorted Array to Binary Search Tree

 

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

题意：给一个升序排好的数组，构造一棵二叉查找树或者叫二叉搜索树BST，要求这颗树是平衡的

BST：二叉查找树，左子树所有节点都小于根节点。右子树所有节点都大于根节点，递归定义

堆（大根堆和小根堆）对应的二叉树：根节点大于所有节点（大根堆），递归定义

解题思路：

1.选数组中间元素插入到BST中。递归实现

2.如果value大于root插入右子树，value小于root插入左子树。递归实现

 

 1 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public TreeNode root ;12 13     public TreeNode sortedArrayToBST(int[] num) {14         if(num.length == 0)15             return root;16         if(1 == num.length){17             return new TreeNode(num[0]);18         }19         int middle = num.length / 2;20         root = new TreeNode(num[middle]);21         22         createBST(num, 0, middle - 1);23         createBST(num, middle + 1, num.length - 1);24         return root;25     }26     27     /**28      * 根据num数组，创建一棵二叉查找树29      * @param num30      * @param start31      * @param end32      */33     private void createBST(int num[], int start, int end){34         int middle = 0;35         if(start <= end && start >= 0 && end <num.length){36             middle = (start + end) / 2;37             38             insertNode(root, num[middle]);39             40             createBST(num, start, middle - 1);41             createBST(num, middle + 1, end);42         }43     }44     45     /**46      * 向root所指的BST二叉查找树中插入value47      * @param root48      * @param value49      */50     private void insertNode(TreeNode root, int value){        51         if(value > root.val){                    //比根节点大,在右子树插入52             if(root.right == null){53                 root.right = new TreeNode(value);54             }else{55                 root = root.right;56                 insertNode(root, value);57             }58         }59         else{60             if(root.left == null){61                 root.left = new TreeNode(value);62             }else{63                 root = root.left;64                 insertNode(root, value);            //比根节点小的插入左子树65             }66         }67     }68     69 //    /**70 //     * 先序遍历71 //     * @param root72 //     */73 //    public void preTravel(TreeNode root){74 //        if(root != null){75 //            System.out.print(root.val + " ");76 //            preTravel(root.left);77 //            preTravel(root.right);78 //        }79 //    }80 }

 

涉及到树的，很多都会用到递归实现，DFS，先序遍历等遍历...

 

 

 

 

Convert Sorted Array to Binary Search Tree


联系
我们