20 February 2020
LeetCode(95) -- 102, 103, 105, 106, 109
by Jerry Zhang
P102. Binary Tree Level Order Traversal (Medium)
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example: Given binary tree [3,9,20,null,null,15,7],
My Solution
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (queue.size() > 0) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.remove();
list.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
ans.add(list);
}
return ans;
}
}
71% 第一次提交出错，记住每次遍历时，是把当前节点的值加入到list中，而不是把他们的子节点加入到list中。queue的作用是预备队。
The Best Solution
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()) {
int size = q.size();
List<Integer> temp = new ArrayList<>();
for(int i=0; i<size; i++) {
TreeNode node = q.poll();
temp.add(node.val);
if ( node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
ans.add(temp);
}
return ans;
}
}
这个最优解代码基本跟我完全一样。
P103. Binary Tree Zigzag Level Order Traversal (Medium)
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
My Solution
public class P103_BinaryTreeZigzagLevelOrderTraversal {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Stack<TreeNode> stack = new Stack<>();
Queue<TreeNode> queue = new LinkedList<>();
boolean leftToRight = true;
stack.push(root);
while (!stack.isEmpty()) {
List<Integer> list = new ArrayList<>();
int size = stack.size();
for (int i = 0; i < size; i++) {
TreeNode pop = stack.pop();
list.add(pop.val);
queue.add(pop);
}
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
if (leftToRight) {
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
} else {
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
leftToRight = !leftToRight;
ans.add(list);
}
return ans;
}
}
74% 过是过了，代码太长。
The Best Solution
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
helper(root, 0, res);
return res;
}
public void helper(TreeNode root, int level, List<List<Integer>> res) {
if (root == null) return;
if (level == res.size()) {//similar logic in right side view
res.add(new LinkedList<Integer>());
}
if (level % 2 == 0) {
res.get(level).add(root.val);
} else {
res.get(level).add(0, root.val);
}
helper(root.left, level + 1, res);
helper(root.right, level + 1, res);
}
}
只有在level和size相等时，才加一个新节点。
P105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]
Solution
基本思路是，从preorder中一个一个看，然后在inorder中找到这个数，左边所有的数构成它的左子树，右边所有的数构成它的右子树。然后做递归。
class Solution {
int pre_idx = 0;
int[] preorder;
int[] inorder;
HashMap<Integer, Integer> idx_map = new HashMap<>();
public TreeNode helper(int in_left, int in_right) {
if (in_left == in_right) {
return null;
}
int root_val = preorder[pre_idx];
TreeNode root = new TreeNode(root_val);
int index = idx_map.get(root_val);
pre_idx++;
root.left = helper(in_left, index);
root.right = helper(index + 1, in_right);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
int idx = 0;
for (Integer val : inorder) {
idx_map.put(val, idx++);
}
return helper(0, inorder.length);
}
}
P106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
Solution
class Solution {
int post_index;
int[] postorder;
int[] inorder;
HashMap<Integer, Integer> map = new HashMap<>();
public TreeNode helper(int left, int right) {
if (left > right) {
return null;
}
int root_val = postorder[post_index];
TreeNode root = new TreeNode(root_val);
Integer index = map.get(root_val);
post_index--;
root.right = helper(index + 1, right);
root.left = helper(left, index - 1);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
this.inorder = inorder;
post_index = postorder.length - 1;
int idx = 0;
for (Integer val: inorder) {
map.put(val, idx++);
}
return helper(0, inorder.length - 1);
}
}
P109. Convert Sorted List to Binary Search Tree (Medium)
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
My Solution
public class P109_ConvertSortedListtoBinarySearchTree {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
ArrayList<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
return arrayListToBST(list, 0, list.size() - 1);
}
private TreeNode arrayListToBST(ArrayList<Integer> list, int l, int r) {
if (l > r) {
return null;
}
if (l == r) {
return new TreeNode(list.get(l));
}
int mid = l + (r - l) / 2;
TreeNode node = new TreeNode(list.get(mid));
TreeNode left = arrayListToBST(list, l, mid - 1);
TreeNode right = arrayListToBST(list, mid + 1, r);
node.left = left;
node.right = right;
return node;
}
}
61% 每次取中点，左右两边设置边界，然后用中点作为根节点，左边的所有数作为左子节点，右边所有数作为右子节点。
Solution
Approach 2: Recursion + Conversion to Array
class Solution {
private List<Integer> values;
public Solution() {
this.values = new ArrayList<Integer>();
}
private void mapListToValues(ListNode head) {
while (head != null) {
this.values.add(head.val);
head = head.next;
}
}
private TreeNode convertListToBST(int left, int right) {
// Invalid case
if (left > right) {
return null;
}
// Middle element forms the root.
int mid = (left + right) / 2;
TreeNode node = new TreeNode(this.values.get(mid));
// Base case for when there is only one element left in the array
if (left == right) {
return node;
}
// Recursively form BST on the two halves
node.left = convertListToBST(left, mid - 1);
node.right = convertListToBST(mid + 1, right);
return node;
}
public TreeNode sortedListToBST(ListNode head) {
// Form an array out of the given linked list and then
// use the array to form the BST.
this.mapListToValues(head);
// Convert the array to
return convertListToBST(0, this.values.size() - 1);
}
}
方法二跟我的一样。
Approach 3: Inorder Simulation
class Solution {
private ListNode head;
private int findSize(ListNode head) {
ListNode ptr = head;
int c = 0;
while (ptr != null) {
ptr = ptr.next;
c += 1;
}
return c;
}
private TreeNode convertListToBST(int l, int r) {
// Invalid case
if (l > r) {
return null;
}
int mid = (l + r) / 2;
// First step of simulated inorder traversal. Recursively form
// the left half
TreeNode left = this.convertListToBST(l, mid - 1);
// Once left half is traversed, process the current node
TreeNode node = new TreeNode(this.head.val);
node.left = left;
// Maintain the invariance mentioned in the algorithm
this.head = this.head.next;
// Recurse on the right hand side and form BST out of them
node.right = this.convertListToBST(mid + 1, r);
return node;
}
public TreeNode sortedListToBST(ListNode head) {
// Get the size of the linked list first
int size = this.findSize(head);
this.head = head;
// Form the BST now that we know the size
return convertListToBST(0, size - 1);
}
}