ConvertSortedArrayToBinarySearchTree [source code]

public class ConvertSortedArrayToBinarySearchTree {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        return build(nums, 0, nums.length - 1);
    }

    public TreeNode build(int[] nums, int lo, int hi) {
        if (lo == hi) return new TreeNode(nums[lo]);
        else if (lo + 1 == hi) {
            TreeNode ret = new TreeNode(nums[hi]);
            ret.left = new TreeNode(nums[lo]);
            return ret;
        }
        else {
            int mid = lo + (hi - lo) / 2;
            TreeNode ret = new TreeNode(nums[mid]);
            ret.left = build(nums, lo, mid - 1);
            ret.right = build(nums, mid + 1, hi);
            return ret;
        }
    }

    public static void main(String[] args) {
        ConvertSortedArrayToBinarySearchTree tester = new ConvertSortedArrayToBinarySearchTree();
    }
}

这个问题的 naive 思路应该还是有的, 直接就用 BST 的 add 来做就行了. 但是这里银库给了一个信息, 就是 sorted 的, 所以肯定有更巧妙的方法; //不对, 这个想法不对, 如果直接随便顺序来 add, 最后得到的完全不能保证是一个 balanced 的 tree, 比如你可以自己尝试一下4123567的顺序进行一个 add. 最后得到的非常不 balanded.

刚开始的时候很想考虑boundary case, 比如最后无法保证所有的 leaf 都是相同 depth. 但是刚开始思考的时候不要思考这么极端的情况. 就用1234567来思考;

sorted一般可以用来干什么? binary search, 2pointers.

刚开始拿到这个题目也是完全无从下手, 结果先是想着写一个 naive 解, 然后居然顺便就想起来了正确的解法怎么写. 一把 AC, 而且是 submission 最优解1ms.

感觉这个问题还是比较有个性的, 简单的想要总结一些什么技巧不是特别现实. 而且用 recursion 反过来写 Tree 这个还是第一次碰到. BST property 就是依靠 sorted 本身来保证的: 用左边的 element 做出来的 subtree 里面的node 肯定全都小于those built from the sublist on the right.
至于 balanced, 就是通过控制size of subtree来完成的. 利用binary search直接将 nums 分段, 这样分出来的就可以保证任何一个 level 都是左右大小尽可能相等.

类似所有的 recursion 问题, 或者叫分治问题, 总是要考虑what the recursive return value is. 其实还要考虑参数是什么. 参数一般要反映一个subproblem的性质, 就是问题在不断被 reduce. 这里的参数就是一个 sublist, 然后返回值就是直接是tree node就行了, 因为 TreeNode 本身自带 DP property, 所以最合适不过.

修改的时候又出现老问题, 忘记考虑empty case, 这里的 case 同样对empty case有进行判断. 尤其这里的代码很依赖array access, 你不判断 empty, 直接就是报错.

下面是两个 iterative 的版本:

public class Solution {      
    public TreeNode sortedArrayToBST(int[] nums) {          
        int len = nums.length;  
        if ( len == 0 ) { return null; }  

        // 0 as a placeholder  
        TreeNode head = new TreeNode(0);   

        Deque<TreeNode> nodeStack       = new LinkedList<TreeNode>() {{ push(head);  }};  
        Deque<Integer>  leftIndexStack  = new LinkedList<Integer>()  {{ push(0);     }};  
        Deque<Integer>  rightIndexStack = new LinkedList<Integer>()  {{ push(len-1); }};  

        while ( !nodeStack.isEmpty() ) {  
            TreeNode currNode = nodeStack.pop();  
            int left  = leftIndexStack.pop();  
            int right = rightIndexStack.pop();  
            int mid   = left + (right-left)/2; // avoid overflow  
            currNode.val = nums[mid];  
            if ( left <= mid-1 ) {  
                currNode.left = new TreeNode(0);    
                nodeStack.push(currNode.left);  
                leftIndexStack.push(left);  
                rightIndexStack.push(mid-1);  
            }  
            if ( mid+1 <= right ) {  
                currNode.right = new TreeNode(0);  
                nodeStack.push(currNode.right);  
                leftIndexStack.push(mid+1);  
                rightIndexStack.push(right);  
            }  
        }  
        return head;  
    }  
}

public class Solution {  
    public TreeNode sortedArrayToBST(int[] nums) {  
        if (nums == null || nums.length == 0) {  
            return null;  
        }  

        Queue<MyNode> queue = new LinkedList<>();  
        int left = 0;  
        int right = nums.length - 1;  
        int val = nums[left + (right - left) / 2];  
        TreeNode root = new TreeNode(val);  
        queue.offer(new MyNode(root, left, right));  

        while (!queue.isEmpty()) {  
            int size = queue.size();  
            for (int i = 0; i < size; i++) {  
                MyNode cur = queue.poll();  

                int mid = cur.lb + (cur.rb - cur.lb) / 2;  

                if (mid != cur.lb) {  
                    TreeNode leftChild = new TreeNode(nums[cur.lb + (mid - 1 - cur.lb) / 2]);  
                    cur.node.left = leftChild;  
                    queue.offer(new MyNode(leftChild, cur.lb, mid - 1));  
                }  

                if (mid != cur.rb) {  
                    TreeNode rightChild = new TreeNode(nums[mid + 1 + (cur.rb - mid - 1) / 2]);  
                    cur.node.right = rightChild;  
                    queue.offer(new MyNode(rightChild, mid + 1, cur.rb));  
                }  
            }  
        }  

        return root;  
    }  

    private static class MyNode {  
        TreeNode node;  
        int lb;  
        int index;  
        int rb;  

        public MyNode(TreeNode n, int theLeft, int theRight) {  
            this.node = n;  
            this.lb = theLeft;  
            this.rb = theRight;  
        }  
    }  
}

我现在其实对 BFS 并不是很熟悉, 所以这两个代码也没什么好说的. 这个问题用 BFS 做确实不错, 从上到下直接做, 能够保证 balanced.
所谓的 BFS, 之所以能够保证bread first, 也就是一个深度一个深度的处理, 保证所有深度 d 的都在深度 d+1的之前被处理完, 就是因为利用的结构拥有 FIFO 的性质.
这两个代码, 第一个还看得懂, 第二个就有点发懵了. 暂时不管了.

Problem Description

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

Difficulty:Easy
Category:Algorithms
Acceptance:41.74%
Contributor: LeetCode
Companies
airbnb
Related Topics
tree depth-first search
Similar Questions
Convert Sorted List to Binary Search Tree