Construst Tree
Last updated
Was this helpful?
Last updated
Was this helpful?
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) return null;
return helper(nums, 0, nums.length - 1);
}
private TreeNode helper(int[] nums, int left, int right) {
if (left == right) return new TreeNode(nums[left]);
if (left > right) return null;
int mid = (right + left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
} def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums or len(nums) == 0:
return None
return self.helper(nums, 0, len(nums) - 1)
def helper(self, nums, L , R):
if L > R:
return None
if L == R:
return TreeNode(nums[L])
mid = L + (R - L) // 2
curt = TreeNode(nums[mid])
curt.left = self.helper(nums, L, mid - 1)
curt.right = self.helper(nums, mid + 1, R)
return curtUse fast and slow pointer to find mid of the list. Construct root as the mid value. Recursively construct root left as value in range Integer.MIN_VALUE and mid.val, root right as value in range mid.val and Integer.MAX_VALUE. Return null if exceed the range.
public TreeNode sortedListToBST(ListNode head) {
return buildTree(head, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode buildTree(ListNode head, int min, int max) {
ListNode mid = getMid(head);
if (mid == null || mid.val <= min || mid.val >= max) return null;
TreeNode root = new TreeNode(mid.val);
root.left = buildTree(head, min, root.val);
root.right = buildTree(mid.next, root.val, max);
return root;
}
private ListNode getMid(ListNode head) {
ListNode pre = new ListNode(-1);
pre.next = head;
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
pre = slow;
fast = fast.next.next;
slow = slow.next;
}
pre.next = null;
return slow;
}Use a StringBuilder to append elements from tree to string.
1
/ \
2 3
/ \
4 5
as "[1,2,3,n,n,4,5]" // Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if (root == null) return "";
serializehelper(root, sb);
return sb.toString();
}
private void serializehelper(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(',').append("n");
return;
}
if (sb.length() == 0) {
sb.append(root.val);
} else {
sb.append(",").append(root.val);
}
serializehelper(root.left, sb);
serializehelper(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.isEmpty()) return null;
Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
return deserialHelper(q);
}
private TreeNode deserialHelper(Queue<String> q) {
if (q.isEmpty()) return null;
String s = q.poll();
if (s.equals("n")) return null;
TreeNode curt = new TreeNode(Integer.valueOf(s));
curt.left = deserialHelper(q);
curt.right = deserialHelper(q);
return curt;
} // Encodes a tree to a single string.
StringBuilder sb = new StringBuilder();
int id = 0;
public String serialize(TreeNode root) {
int rootId = serialHelper(root);
return sb.toString();
}
private int serialHelper(TreeNode root) {
if (root == null) return -1;
id++;
int curtId = id;
int leftId = serialHelper(root.left);
int rightId = serialHelper(root.right);
sb.append(root.val).append(",");
sb.append(curtId).append(",");
sb.append(leftId).append(",");
sb.append(rightId).append(";");
return curtId;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] nodes = data.split(";");
Map<Integer, TreeNode> map = new HashMap<>();
for (int i = 0; i < nodes.length; i++) {
String[] nodedata = nodes[i].split(",");
if (nodedata.length != 4) continue;
int val = Integer.parseInt(nodedata[0]);
int id = Integer.parseInt(nodedata[1]);
int leftid = Integer.parseInt(nodedata[2]);
int rightid = Integer.parseInt(nodedata[3]);
if (!map.containsKey(id)) {
TreeNode node = new TreeNode(val);
map.put(id, node);
} else {
map.get(id).val = val;
}
if (!map.containsKey(leftid) && leftid != -1) {
map.put(leftid, new TreeNode(-1));
}
if (!map.containsKey(rightid) && rightid != -1) {
map.put(rightid, new TreeNode(-1));
}
map.get(id).left = map.get(leftid);
map.get(id).right = map.get(rightid);
}
return map.get(1);
}Use BST characteristics to construct BST.
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if (root != null) helper(sb, root);
return sb.toString();
}
private void helper(StringBuilder sb, TreeNode root) {
sb.append(root.val);
sb.append(",");
if (root.left != null) helper(sb, root.left);
if (root.right != null) helper(sb, root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.isEmpty()) return null;
String[] strs = data.split(",");
Queue<String> q = new LinkedList<>(Arrays.asList(strs));
return decode(q, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode decode(Queue<String> q, int min, int max) {
if (q.isEmpty()) {
return null;
}
if (Integer.parseInt(q.peek()) < min || Integer.parseInt(q.peek()) > max) return null;
int val = Integer.parseInt(q.poll());
TreeNode root = new TreeNode(val);
root.left = decode(q, min, val);
root.right = decode(q, val, max);
return root;
}Construct tree key and count the number of subtrees in the same pattern.
List<TreeNode> res;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
this.res = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
helper(root, map);
return this.res;
}
private String helper(TreeNode root, Map<String, Integer> map) {
if (root == null) {
return "#";
}
String key = root.val + "," + helper(root.left, map) + "," + helper(root.right, map);
map.put(key, map.getOrDefault(key, 0) + 1);
if (map.get(key) == 2) {
this.res.add(root);
}
return key;
}Break a big problem into several small problems. Get all possible combinations under N = 2 then construct the tree according to the combinations. Use memo.
Map<Integer, List<TreeNode>> memo = new HashMap<>();
public List<TreeNode> allPossibleFBT(int N) {
if (N <= 0 || N % 2 == 0) return new ArrayList<>();
if (N == 1) {
List<TreeNode> res = new ArrayList<>();
res.add(new TreeNode(0));
return res;
}
if (memo.containsKey(N)) {
return memo.get(N);
}
List<TreeNode> res = new ArrayList<>();
for (int i = 1; i < N; i += 2) {
List<TreeNode> leftSub = allPossibleFBT(i);
List<TreeNode> rightSub = allPossibleFBT(N - i - 1);
for (TreeNode l : leftSub) {
for (TreeNode r : rightSub) {
TreeNode root = new TreeNode(0);
root.left = l;
root.right = r;
res.add(root);
}
}
}
memo.put(N, res);
return res;
}int index = 0;
public TreeNode bstFromPreorder(int[] preorder) {
return build(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode build(int[] nums, int min, int max) {
if (min > max) return null;
if (index >= nums.length || nums[index] <= min || nums[index] >= max) {
return null;
}
TreeNode root = new TreeNode(nums[index++]);
root.left = build(nums, min, root.val);
root.right = build(nums, root.val, max);
return root;
}public TreeNode bstFromPreorder(int[] preorder) {
int i = 0;
TreeNode root = new TreeNode(preorder[i++]);
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty() && i < preorder.length) {
TreeNode newNode = new TreeNode(preorder[i]);
if (preorder[i] > stack.peek().val) {
TreeNode curt = null;
while (!stack.isEmpty() && preorder[i] > stack.peek().val) {
curt = stack.pop();
}
curt.right = newNode;
} else {
stack.peek().left = newNode;
}
stack.add(newNode);
i++;
}
return root;
}Use a pointer in preorder array to track the next number, also use a L and R boundary in inorder array to define the range. Make a hashmap to store the elements and its corresponding indicies.
Get the index in inorder array, the left node is in inorder range between inL and index - 1, right node is between index + 1 and inR. In preorder, the next left node is i + 1, right is i + size of left range + 1, which is i + inIndex - inLeft + 1
Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return helper(preorder, 0, inorder, 0, inorder.length - 1);
}
private TreeNode helper(int[] preorder,
int index,
int[] inorder,
int inL,
int inR) {
if (inL > inR || index >= preorder.length) {
return null;
}
TreeNode root = new TreeNode(preorder[index]);
int inIndex = map.get(root.val);
root.left = helper(preorder,
index + 1,
inorder,
inL,
inIndex - 1);
root.right = helper(preorder,
index + inIndex - inL + 1,
inorder,
inIndex + 1,
inR);
return root;
}Similar as the question above. Postorder runs opposite as preorder.
Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder == null || inorder == null
|| postorder.length == 0 || inorder.length == 0) return null;
inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) inorderMap.put(inorder[i], i);
return build(postorder.length - 1, 0, inorder.length - 1, postorder);
}
private TreeNode build(int postIndex, int inLeft, int inRight, int[] postorder) {
if (inLeft > inRight || postIndex >= postorder.length) return null;
TreeNode root = new TreeNode(postorder[postIndex]);
int inIndex = inorderMap.get(postorder[postIndex]);
root.left = build(postIndex - (inRight - inIndex + 1),
inLeft,
inIndex - 1,
postorder);
root.right = build(postIndex - 1,
inIndex + 1,
inRight,
postorder);
return root;
}Maintain two ranges.
Map<Integer, Integer> map;
public TreeNode constructFromPrePost(int[] pre, int[] post) {
map = new HashMap<>();
int n = pre.length;
for (int i = 0 ; i < n; i++) {
map.put(post[i], i);
}
return helper(pre, 0, n - 1, post, 0, n - 1);
}
private TreeNode helper(int[] pre, int preL, int preR, int[] post, int postL, int postR) {
if (preL > preR || postL > postR) return null;
TreeNode root = new TreeNode(pre[preL]);
if (preL == preR) {
return root;
}
int delta = map.get(pre[preL + 1]) - postL;
root.left = helper(pre,
preL + 1,
preL + delta + 1,
post,
postL,
postL + delta);
root.right = helper(pre,
preL + 1 + delta + 1,
preR,
post,
postL + delta + 1,
postR - 1);
return root;
}