I understand that this problem can be most naturally solved with recursion. However, I wonder if there is an iterative solution that only uses constant space (aside from the space occupied by the input array and the output tree nodes). For now, the only thing I can think of is Morris Traversal, but I wonder if a simpler solution exists for this particular problem. Any suggestion would be appreciated!
Is there any good iterative O(1) space solution out there?


How do you like this? It's a recursive way, but it doesn't require copy stuff around but just constructs the tree based on given num. I LOVE Python. =)
class Solution: # @param num, a list of integers # @return a tree node def sortedArrayToBST(self, num): def convert_array(left, right): """Convert num[left:right] to a (sub)tree.""" # num[x:x] is an empty list (x is any number) if left >= right: return None # mid point at the very middle of num[left:right] # or the right one of the middle two mid = (left + right) / 2 root = TreeNode(num[mid]) root.left = convert_array(left, mid) root.right = convert_array(mid + 1, right) return root return convert_array(0, len(num))

Build the complete binary tree structure first, then use standard Morris traverse to assign value on each node.
public TreeNode sortedArrayToBST(int[] nums) { int len = nums.length; if(len==0){ return null; } TreeNode root = new TreeNode(0); len; Queue<TreeNode> q = new LinkedList<>(); q.add(root); int layer = 1; while(len>0){ layer *= 2; for(int i=0;i<layer&&len>0;i++,len=2){ TreeNode cur = q.poll(); cur.left = new TreeNode(0); if(len>1){ cur.right = new TreeNode(0); q.add(cur.left); q.add(cur.right); } } } int i=0; TreeNode cur = root; while(cur!=null){ if(cur.left==null){ cur.val = nums[i++]; cur = cur.right; }else { TreeNode pre = cur.left; while(pre.right!=null && pre.right!=cur){ pre = pre.right; } if(pre.right==null){ pre.right = cur; cur = cur.left; }else { pre.right = null; // pre must has a value now cur.val = nums[i++]; cur = cur.right; } } } return root; }