(1) Verify preorder sequence in Binary Search Tree (leetcode 255)
(2) serialize and deserialize binary Tree (leetcode 297)
(3) Recover binary search tree (leetcode 99)
(4) populating next right pointer in each node (leetcode 117)
(5) Convert common ancestor of binary Tree((236) BST(235)
(6) largest BST substree (leetcode 333)
(7) Kth smallest element in BST(leetcode 230) frequent search with modify( node with size infor)
(8) flatten binary tree to linked list(leetcode 114)
(9) count the complete tree node (leetcode 222) try iterative
(10) construct tree from preorder and inorder traversal (leetcode 105)
(11) closest binary search tree value II (leetcode 272) similar: two sum of BST
(12) Binary Tree upside down (leetcode 156)
(13) Binary Tree postorder traversal (leetcode 145)
(14) Binary Tree maximum path sum (leetcode 124)
2016年3月8日星期二
2015年11月6日星期五
Leetcode 297 Serialize and Deserialize Binary Tree
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, you may serialize the following tree
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
Solution 1: use recursive DFS, pre-order traversal.
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb=new StringBuilder();
dfs(root,sb);
return sb.toString();
}
private void dfs(TreeNode x, StringBuilder sb) {
if (x==null) {
sb.append("null ");
return;
}
sb.append(String.valueOf(x.val));
sb.append(' ');
dfs(x.left,sb);
dfs(x.right,sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] node=data.split(" ");
int[] d=new int[1];
return dfs(node,d);
}
private TreeNode dfs(String[] node, int[] d) {
if (node[d[0]].equals("null")) {
d[0]++;
return null;
}
TreeNode x=new TreeNode(Integer.valueOf(node[d[0]]));
d[0]++;
x.left=dfs(node,d);
x.right=dfs(node,d);
return x;
}
}
Solution 2: Use iterative DFS, pre-order traversal.
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb=new StringBuilder();
TreeNode x=root;
Deque<TreeNode> stack=new LinkedList<>();
while (x!=null || !stack.isEmpty()) {
if (x!=null) {
sb.append(String.valueOf(x.val));
sb.append(' ');
stack.push(x);
x=x.left;
}
else {
sb.append("null ");
x=stack.pop();
x=x.right;
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length()==0) return null;
String[] node=data.split(" ");
int n=node.length;
Deque<TreeNode> stack=new LinkedList<>();
TreeNode root=new TreeNode(Integer.valueOf(node[0]));
TreeNode x=root;
stack.push(x);
int i=1;
while (i<n) {
while (i<n && !node[i].equals("null")) {
x.left=new TreeNode(Integer.valueOf(node[i++]));
x=x.left;
stack.push(x);
}
while (i<n && node[i].equals("null")) {
x=stack.pop();
i++;
}
if (i<n) {
x.right=new TreeNode(Integer.valueOf(node[i++]));
x=x.right;
stack.push(x);
}
}
return root;
}
}
Solution 3: Use BFS
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root==null) return "";
Queue<TreeNode> qu=new LinkedList<>();
StringBuilder sb=new StringBuilder();
qu.offer(root);
sb.append(String.valueOf(root.val));
sb.append(' ');
while (!qu.isEmpty()) {
TreeNode x=qu.poll();
if (x.left==null) sb.append("null ");
else {
qu.offer(x.left);
sb.append(String.valueOf(x.left.val));
sb.append(' ');
}
if (x.right==null) sb.append("null ");
else {
qu.offer(x.right);
sb.append(String.valueOf(x.right.val));
sb.append(' ');
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length()==0) return null;
String[] node=data.split(" ");
Queue<TreeNode> qu=new LinkedList<>();
TreeNode root=new TreeNode(Integer.valueOf(node[0]));
qu.offer(root);
int i=1;
while (!qu.isEmpty()) {
Queue<TreeNode> nextQu=new LinkedList<>();
while (!qu.isEmpty()) {
TreeNode x=qu.poll();
if (node[i].equals("null")) x.left=null;
else {
x.left=new TreeNode(Integer.valueOf(node[i]));
nextQu.offer(x.left);
}
i++;
if (node[i].equals("null")) x.right=null;
else {
x.right=new TreeNode(Integer.valueOf(node[i]));
nextQu.offer(x.right);
}
i++;
}
qu=nextQu;
}
return root;
}
}
2015年11月5日星期四
Leetcode 295 Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples: [2,3,4] , the median is 3[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
- void addNum(int num) - Add a integer number from the data stream to the data structure.
- double findMedian() - Return the median of all elements so far.
For example:
add(1) add(2) findMedian() -> 1.5 add(3) findMedian() -> 2
Solution 1: Use BST with size of sub-tree in the node will solve the question. add and find operation will be O(logn) complexity.
class MedianFinder {
public class TreeNode {
private int val;
private int size;
private TreeNode left, right;
public TreeNode(int num) {
val=num;
size=1;
}
}
private TreeNode root=null;
// Adds a number into the data structure.
public void addNum(int num) {
root=addNum(root, num);
}
private TreeNode addNum(TreeNode x, int num) {
if (x==null) return new TreeNode(num);
x.size++;
if (num>x.val) x.right=addNum(x.right,num);
if (num<x.val) x.left=addNum(x.left,num);
return x;
}
// Returns the median of current data stream
public double findMedian() {
int n=root.size;
if (n%2==1) return find(root,n/2+1);
return (double)(find(root,n/2)+find(root,n/2+1))/2;
}
private int find(TreeNode x, int k) {
if (size(x.left)>=k) return find(x.left,k);
if (x.size-size(x.right)<k) return find(x.right,k-x.size+x.right.size);
return x.val;
}
private int size(TreeNode x) {
if (x==null) return 0;
return x.size;
}
}
Leetcode 285 Inorder Successor in BST
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Note: If the given node has no in-order successor in the tree, return
null.
Solution 1: binary search the value>v
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode x=root;
TreeNode res=null;
while (x!=null) {
if (x.val>p.val) {
res=x;
x=x.left;
}
else x=x.right;
}
return res;
}
}
Leetcode 272 Closest Binary Search Tree Value II
Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
- Given target value is a floating point.
- You may assume k is always valid, that is: k ≤ total nodes.
- You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
Solution 1: travel through the BST to build stack left stack and right stack. Each time find the min peek of the two, pop and rebuild one of the stack.
public class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
Deque<TreeNode> left=new LinkedList<>();
Deque<TreeNode> right=new LinkedList<>();
TreeNode x=root;
while (x!=null) {
if (x.val>target) {
right.push(x);
x=x.left;
}
else {
left.push(x);
x=x.right;
}
}
List<Integer> res=new ArrayList<>();
while (res.size()<k) {
if (left.isEmpty()) nextRight(right,res);
else if (right.isEmpty()) nextLeft(left,res);
else if (target-left.peek().val<right.peek().val-target) nextLeft(left,res);
else nextRight(right,res);
}
return res;
}
private void nextRight(Deque<TreeNode> right, List<Integer> res) {
TreeNode x=right.pop();
res.add(x.val);
x=x.right;
while (x!=null) {
right.push(x);
x=x.left;
}
}
private void nextLeft(Deque<TreeNode> left, List<Integer> res) {
TreeNode x=left.pop();
res.add(x.val);
x=x.left;
while (x!=null) {
left.push(x);
x=x.right;
}
}
}
Leetcode 270 Closest Binary Search Tree Value
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
- Given target value is a floating point.
- You are guaranteed to have only one unique value in the BST that is closest to the target.
public class Solution {
public int closestValue(TreeNode root, double target) {
TreeNode x=root;
int res=x.val;
while (x!=null) {
if (target>x.val) x=x.right;
else if (target<x.val) x=x.left;
else return x.val;
if (x!=null && Math.abs(target-x.val)<Math.abs(target-res)) res=x.val;
}
return res;
}
}
2015年11月4日星期三
Leetcode 257 Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1 / \ 2 3 \ 5
All root-to-leaf paths are:
["1->2->5", "1->3"]
Solution 1: DFS
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<Integer> one=new ArrayList<>();
List<String> res=new ArrayList<>();
if (root!=null) dfs(root,one,res);
return res;
}
private void dfs(TreeNode x, List<Integer> one, List<String> res) {
one.add(x.val);
if (x.left!=null) dfs(x.left,one,res);
if (x.right!=null) dfs(x.right,one,res);
if (x.left==null && x.right==null) {
StringBuilder sb=new StringBuilder();
for (int num: one) {
sb.append(String.valueOf(num));
sb.append("->");
}
res.add(sb.substring(0,sb.length()-2));
}
one.remove(one.size()-1);
}
}
Leetcode 255 Verify Preorder Sequence in Binary Search Tree
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.
Follow up:
Could you do it using only constant space complexity?
Could you do it using only constant space complexity?
Solution 1: Use iterative pre-order traversal.
public class Solution {
public boolean verifyPreorder(int[] preorder) {
int n=preorder.length;
int i=0, lo=Integer.MIN_VALUE;
Deque<Integer> stack=new LinkedList<>();
while (i<n) {
if (stack.isEmpty() || preorder[i]<stack.peek()) {
if (preorder[i]<=lo) return false;
stack.push(preorder[i++]);
}
else if (preorder[i]==stack.peek()) return false;
else lo=stack.pop();
}
return true;
}
}
Leetcode 239 Sliding Window Maximum
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums =
Given nums =
[1,3,-1,-3,5,3,6,7], and k = 3.Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Therefore, return the max sliding window as
[3,3,5,5,6,7].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?
Could you solve it in linear time?
Solution 1: Use TreeMap to store the window, the complexity is O(nlogk).
Solution 2: Use deque. When slide the window, remove all the element smaller then new element from right and remove element that pass the left window. The most left element of the deque is always the largest one of the window. Complexity is O(n).
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> dq=new LinkedList<>();
int n=nums.length;
if (n==0 || k==0) return new int[0];
int[] res=new int[n-k+1];
for (int j=0; j<n; j++) {
while (!dq.isEmpty() && nums[dq.peekLast()]<=nums[j]) dq.pollLast();
dq.addLast(j);
if (j>=k-1) {
if (dq.peekFirst()<j-k+1) dq.pollFirst();
res[j-k+1]=nums[dq.peekFirst()];
}
}
return res;
}
}
Leetcode 236 Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
For example, the lowest common ancestor (LCA) of nodes
5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Solution 1: use DFS and return value; (1) if not found any node return null (2) if found one, return the one (3) if find both return current node. (4) at root, the return node will be LCA. Complex is O(n).
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root==null) return null;
if (root==p) return p;
if (root==q) return q;
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if (left==null) {
if (right==null) return null;
else return right;
}
else if (right==null) return left;
else return root;
}
}
Leetcode 235 Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes
2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Solution 1: since it is BST, it can be found with O(logn)
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode x=root;
while (x!=null) {
if (x.val<p.val && x.val<q.val) x=x.right;
else if (x.val>p.val && x.val>q.val) x=x.left;
else return x;
}
return x;
}
}
2015年11月3日星期二
Leetcode 230 Kth Smallest Element in a BST
Given a binary search tree, write a function
kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Solution 1: use in-order traversal and counter the kth number.
public class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack=new LinkedList<>();
TreeNode x=root;
while (x!=null || !stack.isEmpty()) {
if (x!=null) {
stack.push(x);
x=x.left;
}
else {
x=stack.pop();
if (--k==0) return x.val;
x=x.right;
}
}
return 0;
}
} Leetcode 227 Invert Binary Tree
Invert a binary tree.
4 / \ 2 7 / \ / \ 1 3 6 9to
4 / \ 7 2 / \ / \ 9 6 3 1Solution 1: recursive
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root==null) return null;
TreeNode left=invertTree(root.left);
TreeNode right=invertTree(root.right);
root.left=right;
root.right=left;
return root;
}
}
public class Solution {
public TreeNode invertTree(TreeNode root) {
Deque<TreeNode> stack=new LinkedList<>();
if (root==null) return null;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode x=stack.pop();
TreeNode left=x.left;
x.left=x.right;
x.right=left;
if (x.left!=null) stack.push(x.left);
if (x.right!=null) stack.push(x.right);
}
return root;
}
}
public class Solution {
public TreeNode invertTree(TreeNode root) {
Queue<TreeNode> qu=new LinkedList<>();
if (root==null) return null;
qu.offer(root);
while (!qu.isEmpty()) {
TreeNode x=qu.poll();
if (x.left!=null) qu.offer(x.left);
if (x.right!=null) qu.offer(x.right);
TreeNode left=x.left;
x.left=x.right;
x.right=left;
}
return root;
}
}
Leetcode 222 Count Complete Tree Nodes
Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.
Solution 1: Use binary search. Each time check the left sub tree and right sub tree. One of them will be full filled and simple cal the result. The other one is not full filled and will be sub problem of root case. Complexity will be O(logn*logn)
public class Solution {
public int countNodes(TreeNode root) {
if (root==null) return 0;
int left=0, right=0;
TreeNode l=root, r=root;
while (l!=null) {
l=l.left;
left++;
}
while (r!=null) {
r=r.right;
right++;
}
if (left==right) return (1<<left)-1;
return countNodes(root.left)+countNodes(root.right)+1;
}
}
Leetcode 220 Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
Solution 1: compare to II, use Tree Map instead of Hashmap could solve it.
Solution 1: compare to II, use Tree Map instead of Hashmap could solve it.
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int n=nums.length, i=0;
if (t<0) return false;
TreeSet<Integer> set=new TreeSet<>();
for (int j=0; j<n; j++) {
if (j-i>k) set.remove(nums[i++]);
int lo=(nums[j]<Integer.MIN_VALUE+t)?Integer.MIN_VALUE:nums[j]-t;
int hi=(nums[j]>Integer.MAX_VALUE-t)?Integer.MAX_VALUE:nums[j]+t;
if (set.ceiling(lo)!=null && set.ceiling(lo)<=hi) return true;
set.add(nums[j]);
}
return false;
}
}
2015年10月24日星期六
Leetcode 199 Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
Given the following binary tree,
1 <--- / \ 2 3 <--- \ \ 5 4 <---
You should return
[1, 3, 4].
Solution 1: Use BFS iterative is better way.
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res=new ArrayList<>();
if (root==null) return res;
Deque<TreeNode> qu=new LinkedList<>();
Deque<TreeNode> next=new LinkedList<>();
qu.offer(root);
while (!qu.isEmpty()) {
TreeNode x=null;
while (!qu.isEmpty()) {
x=qu.poll();
if (x.left!=null) next.offer(x.left);
if (x.right!=null) next.offer(x.right);
}
res.add(x.val);
Deque<TreeNode> temp=qu;
qu=next;
next=temp;
}
return res;
} Leetcode 173 Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling
next() will return the next smallest number in the BST.
Note:
next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
Solution 1: Use iterative in-order traversal.
public class BSTIterator {
private TreeNode x;
private Deque<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack=new LinkedList<>();
x=root;
while (x!=null) {
stack.push(x);
x=x.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
/** @return the next smallest number */
public int next() {
x=stack.pop();
int res=x.val;
x=x.right;
while (x!=null) {
stack.push(x);
x=x.left;
}
return res;
}
}}
2015年10月15日星期四
Leetcode 156 Binary Tree Upside Down
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:Given a binary tree
{1,2,3,4,5},1 / \ 2 3 / \ 4 5
return the root of the binary tree
[4,5,2,#,#,3,1]. 4
/ \
5 2
/ \
3 1
Solution 1: like linked list reverse.
public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode left=null, p=null, x=root;
while (x!=null) {
TreeNode nextX=x.left;
TreeNode nextL=x.right;
x.right=p;
x.left=left;
p=x;
x=nextX;
left=nextL;
}
return p;
}
}
Leetcode 145 Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree
Given binary tree
{1,#,2,3}, 1
\
2
/
3
return
[3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
Solution 1: Recursive DFS, too easy, similar to pre-order.
Solution 2: Iterative DFS.
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack=new LinkedList<>();
List<Integer> res=new ArrayList<>();
TreeNode x=root;
TreeNode last=null;
while (x!=null || !stack.isEmpty()) {
if (x!=null) {
stack.push(x);
x=x.left;
}
else {
TreeNode peek=stack.peek();
if (peek.right==null || peek.right==last) {
last=stack.pop();
res.add(last.val);
}
else {
x=peek.right;
}
}
}
return res;
}
}
Leetcode 144 Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree
Given binary tree
{1,#,2,3}, 1
\
2
/
3
return
[1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
Solution 1: recursive DFS
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
dfs(root,res);
return res;
}
private void dfs(TreeNode x, List<Integer> res) {
if (x==null) return;
res.add(x.val);
dfs(x.left, res);
dfs(x.right, res);
}
}
Solution 2: iterative DFS
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Deque<TreeNode> stack=new LinkedList<>();
List<Integer> res=new ArrayList<>();
TreeNode x=root;
while (x!=null || !stack.isEmpty()) {
if (x!=null) {
res.add(x.val);
stack.push(x);
x=x.left;
}
else {
x=stack.pop();
x=x.right;
}
}
return res;
}
}
订阅：
博文 (Atom)