本文共 1394 字,大约阅读时间需要 4 分钟。
Convert Sorted Array to Binary Search Tree
package com.leetcode;import java.util.Arrays;public class Test_20 { public static TreeNode sortedArrayToBST(int[] num) { return sortedArrayToBSTUTL(num, 0, num.length - 1); } public static TreeNode sortedArrayToBSTUTL(int[] num, int start, int end) { if (num == null || start > end) return null; int len = end - start; TreeNode root = new TreeNode(0); if (0 == len) { root.val = num[start]; return root; } if (len % 2 == 1) { root.val = num[start + len / 2 + 1]; root.left = sortedArrayToBSTUTL(num, start, start + len / 2); root.right = sortedArrayToBSTUTL(num, start + len / 2 + 2, end); } else { root.val = num[start + len / 2]; root.left = sortedArrayToBSTUTL(num, start, start + len / 2 - 1); root.right = sortedArrayToBSTUTL(num, start + len / 2 + 1, end); } return root; } public static void preOrderTraverse(TreeNode node) { if (node == null) return; preOrderTraverse(node.left); System.out.print(node.val + " "); //preOrderTraverse(node.left); preOrderTraverse(node.right); } public static void main(String[] arqs) { int[] num = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 ,9}; TreeNode root =sortedArrayToBST(num); preOrderTraverse(root); }}
转载地址:http://uiuni.baihongyu.com/