leetcode Daily Challenge on December 3rd, 2020.
Difficulty : Easy
Related Topics : DFS、Tree
Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8 / / \ 1 7 9 Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9
- e number of nodes in the given tree will be between
1
and100
.- Each node will have a unique integer value from
0
to1000
.
- java
-
mine
DFS
Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.4 MB, less than 100.00% of Java online submissions
public TreeNode increasingBST(TreeNode root) { List<Integer> list = new ArrayList<>(); dfs(root, list); Integer[] arr = new Integer[list.size()]; Arrays.sort(list.toArray(arr)); TreeNode res = new TreeNode(arr[0]); TreeNode temp = res; int index = 1; while(index < list.size()){ TreeNode node = new TreeNode(arr[index]); temp.right = node; temp = node; index++; } return res; } public void dfs(TreeNode node, List<Integer> list){ if(node == null){ return; } list.add(node.val); dfs(node.left,list); dfs(node.right,list); }
-
the most votes
Runtime: 0 ms, faster than 100.00%,Memory Usage: 36.9 MB, less than 100.00% of Java online submissions
//O(N)Time O(height)Space public TreeNode increasingBST(TreeNode root) { return increasingBST(root, null); } public TreeNode increasingBST(TreeNode root, TreeNode tail) { if (root == null) return tail; TreeNode res = increasingBST(root.left, root); root.left = null; root.right = increasingBST(root.right, tail); return res; }
-