Convert Sorted Array to Binary Search Tree With Minimal Height

Question:

Given a sorted (increasing order) array, Convert it to create a binary tree with minimal height.

Lesson Learned

• 如果不是final，不能用大写字母表示一个variable
• line 22: 'root' hides a field.
• 要把tree连起来肯定要有一个node.left = new node的过程，不能只定义new node
• 已经把middle加上去了就不用管middle了,也就是说，处理完的数据不应该再recursion了。

• 把node.left和node.right的传递过程其实就是新建一个指针指向left或right的过程。如果不再用函数传递，则需要一个新建指针指向root.left或root.right.否则指针一直指向root会一直改变root的值而整个tree没有被新建起来

    TreeNode node = new TreeNode(array[middle]);
  

Code:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param A: an integer array
     * @return: a tree node
     */
    private TreeNode node = null;
    // 如果不是final，不能用大写字母表示一个variable
    // line 22: 'root' hides a field.
    public TreeNode sortedArrayToBST(int[] array) {
        return sortedArrayToBST(array, node, 0, array.length - 1);
    }
    private TreeNode sortedArrayToBST(int[] array, TreeNode node, int left, int right) {  
        // write your code here
        // 先divide
        if (left > right) {
            return null;
        }
        if (left == right) {
            node = new TreeNode(array[left]);
            return node;
        }

        int middle = left + (right - left) / 2;
        node = new TreeNode(array[middle]);
        // 已经把middle加上去了就不用管middle了！
        // 要把tree连起来肯定要有一个node.left = new node的过程，不能只定义new node
        node.left = sortedArrayToBST(array, node.left, left, middle - 1);
        node.right = sortedArrayToBST(array, node.right, middle + 1, right);
        return node;
    }
}

Updated

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param A: an integer array
     * @return: a tree node
     */
    // 如果不是final，不能用大写字母表示一个variable
    // line 22: 'root' hides a field.
    public TreeNode sortedArrayToBST(int[] array) {
        return sortedArrayToBST(array, 0, array.length - 1);
    }
    private TreeNode sortedArrayToBST(int[] array, int left, int right) {  
        // write your code here
        // 先divide
        if (left > right) {
            return null;
        }

        int middle = left + (right - left) / 2;
        // 把node.left和node.right的传递过程其实就是新建一个指针指向left或
        // right的过程。如果不再用函数传递，则需要一个新建指针指向root.left
        // 或root.right.否则指针一直指向root会一直改变root的值而整个tree没有被
        // 新建起来
        TreeNode node = new TreeNode(array[middle]);
        // 已经把middle加上去了就不用管middle了！
        // 要把tree连起来肯定要有一个node.left = new node的过程，不能只定义new node
        node.left = sortedArrayToBST(array, left, middle - 1);
        node.right = sortedArrayToBST(array, middle + 1, right);
        return node;
    }
}