Hi, your solution is using not O(h) but O(n) memory since you cached the entire tree by calling inOrder(root, inorder) upon construction. I knew the question asked for a limit of O(h) memory, but isn't O(1) even better? :)
flacosun
@flacosun
Posts made by flacosun

RE: Java solution taking O(1) space and O(1) time, beating 99% submissions.

Concise Java Solution
public class Solution { public List<Integer> spiralOrder(int[][] matrix) { int m, n; if ((m = matrix.length) == 0  (n = matrix[0].length) == 0) { return new ArrayList<>(); } List<Integer> order = new ArrayList<>(); // bounds of top, right, bottom and left (in spiral order) int[] bounds = new int[]{0, n  1, m  1, 0}; // directions: 0 for right, 1 for down, 2 for left and 3 for up int direction = 0; while (bounds[0] <= bounds[2] && bounds[1] >= bounds[3]) { // start and end bounds are stored in bounds[last direction] and bounds[next direction], respectively. int start = bounds[(direction + 4  1) % 4]; int end = bounds[(direction + 4 + 1) % 4]; while (true) { if (direction % 2 == 0) { order.add(matrix[bounds[direction]][start]); } else { order.add(matrix[start][bounds[direction]]); } if (start == end) { break; } start += start > end ? 1 : 1; } // update bound bounds[direction] += direction == 0  direction == 3 ? 1 : 1; // turn direction direction = (direction + 1) % 4; } return order; } }

RE: Short Java solution using DP O(n log n)
Hi guys, I understand this works great, but I'm confused why this approach is a DP? Can anyone give a recurrence relation for it? Thank you.

RE: C++ UnionFind amotrized O(n)
For those who are interested in unionfind, here is a tutorial from Princeton U:
I have a similar solution in Java, runtime is 15 ms:
public class Solution { private int n; private int ids[]; private int sizes[]; private int maxSize; public int longestConsecutive(int[] nums) { if ((n = nums.length) == 0) return 0; sizes = new int[n]; ids = new int[n]; Map<Integer, Integer> map = new HashMap<>(); Arrays.fill(sizes, 1); maxSize = 1; for (int i = 0; i < n; i++) { if (map.containsKey(nums[i])) { continue; } map.put(nums[i], i); ids[i] = i; if (map.containsKey(nums[i]  1)) { unite(i, map.get(nums[i]  1)); } if (map.containsKey(nums[i] + 1)) { unite(i, map.get(nums[i] + 1)); } } return maxSize; } private void unite(int a, int b) { int rootA = findRoot(a); int rootB = findRoot(b); if (rootA == rootB) { return; } int small; int large; if (sizes[rootA] > sizes[rootB]) { small = rootB; large = rootA; } else { small = rootA; large = rootB; } ids[small] = large; sizes[large] += sizes[small]; if (sizes[large] > maxSize) { maxSize = sizes[large]; } } private int findRoot(int i) { while (i != ids[i]) { ids[i] = ids[ids[i]]; i = ids[i]; } return i; } }

Java unionfind with path compression and weighted union
Currently its run time is 17 ms. Can this be further improved?

RE: Solve it using Union Find
Nice thought. I came up with this Java unionfind with path compression and weighted union. Currently its run time is 17 ms. Can this be further improved? Thank you.
public class Solution { private int[] ids; // Weight (size) of each union set private int[] sizes; // The id of union set for 'O's on edge private int OOnEdge; int m; int n; public void solve(char[][] board) { if((m = board.length) == 0  (n = board[0].length) == 0) return; ids = new int[m * n]; sizes = new int[m * n]; Arrays.fill(sizes, 1); OOnEdge = 1; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'X') { continue; } int index = i * n + j; ids[index] = index; // Nodes on edges if (i == 0  j == 0  i == m  1  j == n  1) { if (OOnEdge == 1) { // Set OOnEdge if it has not been set yet OOnEdge = index; } else { // If OOnEdge is already set, unite it with index unite(OOnEdge, index); } } // Unite node with its upper neighbor if (i > 0 && board[i  1][j] == 'O') { unite(index, index  n); } // Unite node with its left neighbor if (j > 0 && board[i][j  1] == 'O') { unite(index, index  1); } } } // Find for (int i = 1; i < m  1; i++) { for (int j = 1; j < n  1; j++) { if (board[i][j] == 'X') { continue; } int index = i * n + j; if (OOnEdge == 1  !find(index, OOnEdge)) { board[i][j] = 'X'; } } } } private void unite(int a, int b){ int i = findRoot(a); int j = findRoot(b); // Weighted quick union if (sizes[i] < sizes[j]) { ids[i] = j; sizes[j] += sizes[i]; } else { ids[j] = i; sizes[i] += sizes[j]; } } private boolean find(int a, int b){ return findRoot(a) == findRoot(b); } private int findRoot(int i) { while (i != ids[i]) { // Path compression ids[i] = ids[ids[i]]; i = ids[i]; } return i; } }

RE: Morris Traversal, O(n) time, O(1) space, can be applied to inorder and postorder
Nice solution! I applied your idea to postorder traversal

Simple 1ms Java solution using O(1) extra space (Morris Traversal)
The key to keeping the solution simple is to add the element from the front of the result list. Then the problem becomes a mirrored version of Morris preorder traversal
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); while (root != null) { if (root.right == null) { result.add(0, root.val); root = root.left; } else { TreeNode predecessor = root.right; while (predecessor.left != null && predecessor.left != root) { predecessor = predecessor.left; } if (predecessor.left == null) { predecessor.left = root; result.add(0, root.val); root = root.right; } else { predecessor.left = null; root = root.left; } } } return result; } }

Java solution taking O(1) space and O(1) time, beating 99% submissions.
A typical Morris traversal approach.
public class BSTIterator { private TreeNode current; public BSTIterator(TreeNode root) { current = threadAllNodesOnLeftMostBranch(root); } /** @return whether we have a next smallest number */ public boolean hasNext() { return current != null; } /** @return the next smallest number */ public int next() { int result = current.val; current = current.right; // If thread(current) returns false, it means that the left sub tree of current is visited. // So there's no need to call threadAllNodesOnLeftMostBranch on current. if (current != null && current.left != null && thread(current)) { // current is already threaded in the if statement, skip it. current = current.left; current = threadAllNodesOnLeftMostBranch(current); } return result; } // Thread all nodes on TreeNode root's leftmost branch until it reaches the last node on the branch, // and return the last node private TreeNode threadAllNodesOnLeftMostBranch(TreeNode root) { while (root != null && root.left != null) { thread(root); root = root.left; } return root; } // Thread or unthread TreeNode root with its successor // Return true if the operation turns out as a threading, and false if unthreading. private boolean thread(TreeNode root) { TreeNode predecessor = root.left; while (predecessor.right != null && predecessor.right != root) { predecessor = predecessor.right; } if (predecessor.right == null) { predecessor.right = root; return true; } else { predecessor.right = null; return false; } } }
These solutions also take O(1) space and O(1) time:
The most voted one has an overhead for threading the tree, it's not as fast as other solutions.
A good approach which does not break the tree, the implementation not very concise.

Java solution using a linked list
The idea is similar to this popular solution or this. The only difference here is that a linked list is used instead of array. For this problem a linked list may be more space saving as nodes which all 3 pointers have left will be released from memory.
public class Solution { public int nthUglyNumber(int n) { ListNode current = new ListNode(1); ListNode n2 = current; ListNode n3 = current; ListNode n5 = current; for (int i = 2; i <= n; i++) { int min = Math.min(n2.val * 2, Math.min(n3.val * 3, n5.val * 5)); current.next = new ListNode(min); current = current.next; n2 = n2.val * 2 == min ? n2.next : n2; n3 = n3.val * 3 == min ? n3.next : n3; n5 = n5.val * 5 == min ? n5.next : n5; } return current.val; } private class ListNode { private int val; private ListNode next; private ListNode(int value) { val = value; } } }