例题
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.
public class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> ret = new LinkedList<>();
Stack<TreeNode> succ = new Stack<>();
Stack<TreeNode> pred = new Stack<>();
initializePredecessorStack(root, target, pred);
initializeSuccessorStack(root, target, succ);
if(!succ.isEmpty() && !pred.isEmpty() && succ.peek().val == pred.peek().val) {
getNextPredecessor(pred);
}
while(k-- > 0) {
if(succ.isEmpty()) {
ret.add(getNextPredecessor(pred));
} else if(pred.isEmpty()) {
ret.add(getNextSuccessor(succ));
} else {
double succ_diff = Math.abs((double)succ.peek().val - target);
double pred_diff = Math.abs((double)pred.peek().val - target);
if(succ_diff < pred_diff) {
ret.add(getNextSuccessor(succ));
} else {
ret.add(getNextPredecessor(pred));
}
}
}
return ret;
}
private void initializeSuccessorStack(TreeNode root, double target, Stack<TreeNode> succ) {
while(root != null) {
if(root.val == target) {
succ.push(root);
break;
} else if(root.val > target) {
succ.push(root);
root = root.left;
} else {
root = root.right;
}
}
}
private void initializePredecessorStack(TreeNode root, double target, Stack<TreeNode> pred) {
while(root != null){
if(root.val == target){
pred.push(root);
break;
} else if(root.val < target){
pred.push(root);
root = root.right;
} else{
root = root.left;
}
}
}
private int getNextSuccessor(Stack<TreeNode> succ) {
TreeNode curr = succ.pop();
int ret = curr.val;
curr = curr.right;
while(curr != null) {
succ.push(curr);
curr = curr.left;
}
return ret;
}
private int getNextPredecessor(Stack<TreeNode> pred) {
TreeNode curr = pred.pop();
int ret = curr.val;
curr = curr.left;
while(curr != null) {
pred.push(curr);
curr = curr.right;
}
return ret;
}
}
Search Range in Binary Search Tree
Given a binary search tree and a range [k1, k2], return node values within a given range in ascending order.
public class Solution {
/**
* @param root: param root: The root of the binary search tree
* @param k1: An integer
* @param k2: An integer
* @return: return: Return all keys that k1<=key<=k2 in ascending order
*/
public List<Integer> searchRange(TreeNode root, int k1, int k2) {
// write your code here
List<Integer> ans = new ArrayList<>();
dfs(root, k1, k2, ans);
return ans;
}
private void dfs(TreeNode root, int k1, int k2, List<Integer> ans){
if(root == null) return;
if(root.val >= k1 && root.val <= k2){
dfs(root.left, k1, k2, ans);
ans.add(root.val);
dfs(root.right, k1, k2, ans);
}else if(root.val < k1){
dfs(root.right, k1, k2, ans);
}else{
dfs(root.left, k1, k2, ans);
}
}
}
Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
- A single node tree is a BST
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
public boolean isValidBST(TreeNode root) {
// write your code here
return helper(root, null, null);
}
private boolean helper(TreeNode root, Integer min, Integer max){
if(root == null) return true;
if((min != null && root.val <= min) || (max != null && root.val >= max)) return false;
return helper(root.left, min, root.val) && helper(root.right, root.val, max);
}
}
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.
public class Solution {
/**
* @param root: the root of binary tree
* @return: new root
*/
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root == null) return null;
if(root.left == null) return root;
//root会成为它本来的left child的right child
//root本来的right child会成为root的left child的left child
TreeNode new_root = upsideDownBinaryTree(root.left);
root.left.left = root.right;
root.left.right = root;
root.left = null;
root.right = null;
return new_root;
}
}
Find Leaves of Binary Tree
Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.
//{1,2,3,4,5}
//node的depth就是这个node应该在list里的位置
//注意：depth和height不一样，例如1的depth是3， 2的的depth是2， 3的depth是1， 4和5的depth也是1
public class Solution {
/*
* @param root: the root of binary tree
* @return: collect and remove all leaves
*/
public List<List<Integer>> findLeaves(TreeNode root) {
// write your code here
List<List<Integer>> ans = new ArrayList<>();
if(root == null) return ans;
dfs(root, ans);
return ans;
}
private int dfs(TreeNode root, List<List<Integer>> ans){
if(root == null) return 0;
int depth = Math.max(dfs(root.left, ans), dfs(root.right, ans));
if(ans.size() <= depth){
ans.add(new ArrayList<Integer>());
}
ans.get(depth).add(root.val);
return depth + 1;
}
}
Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
class Pair{
TreeNode root;
ListNode next;
public Pair(TreeNode root, ListNode next){
this.root = root;
this.next = next;
}
}
public class Solution {
/*
* @param head: The first node of linked list.
* @return: a tree node
*/
public TreeNode sortedListToBST(ListNode head) {
// write your code here
if(head == null) return null;
int size = get_size(head);
return helper(head, size).root;
}
private int get_size(ListNode head){
int size = 0;
while(head != null){
head = head.next;
size++;
}
return size;
}
//return root, and the ListNode after size / 2
private Pair helper(ListNode head, int size){
if(size == 0) return new Pair(null, head);
Pair left = helper(head, size / 2);
Pair right = helper(left.next.next, size - (size / 2) - 1);
TreeNode root = new TreeNode(left.next.val);
root.left = left.root;
root.right = right.root;
return new Pair(root, right.next);
}
}
Inorder Predecessor in BST
Given a binary search tree and a node in it, find the in-order predecessor of that node in the BST.
public class Solution {
/**
* @param root: the given BST
* @param p: the given node
* @return: the in-order predecessor of the given node in the BST
*/
public TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
// write your code here
//返回rightmost child of p’s left subtree 或者 lowest left parent
return helper(root, p, null);
}
private TreeNode helper(TreeNode root, TreeNode p, TreeNode lowest_left_parent){
if(root == null) return null;
if(root.val == p.val){
if(root.left == null) {
return lowest_left_parent;
}else{
root = root.left;
while(root.right != null){
root = root.right;
}
return root;
}
}else if(root.val < p.val){
return helper(root.right, p, root);
}else{
return helper(root.left, p, lowest_left_parent);
}
}
}
heir tree
-lazy delete
public class MyTreeNode {
/**
* @param val: the val of the node
* @return: a MyTreeNode Object
*/
List<MyTreeNode> children;
int val;
boolean deleted;
MyTreeNode(int val) {
// write your code here
this.val = val;
this.children = new ArrayList<>();
this.deleted = false;
}
/**
* @param root: the root treenode
* @return: get the traverse of the treenode
*/
public ArrayList<Integer> traverse(MyTreeNode root) {
// write your code here
ArrayList<Integer> inheritance = new ArrayList<>();
traverse_helper(root, inheritance);
return inheritance;
}
private void traverse_helper(MyTreeNode root, ArrayList<Integer> inheritance){
if(root != null && !root.deleted) {
inheritance.add(root.val);
}
for(MyTreeNode c : root.children){
traverse_helper(c, inheritance);
}
}
/**
* @param root: the node where added
* @param value: the added node's value
* @return: add a node, return the node
*/
public MyTreeNode addNode(MyTreeNode root, int value) {
// write your code here
MyTreeNode new_node = new MyTreeNode(value);
root.children.add(new_node);
return new_node;
}
/**
* @param root: the deleted node
* @return: nothing
*/
public void deleteNode(MyTreeNode root) {
// write your code here
root.deleted = true;
}
}
Flatten Binary Tree to Linked List
Flatten a binary tree to a fake "linked list" in pre-order traversal. Here we use the right pointer in TreeNode as the next pointer in ListNode.
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void flatten(TreeNode root) {
// write your code here
dfs(root);
}
//return the last node of the converted linked list
private TreeNode dfs(TreeNode root){
if(root == null) return root;
TreeNode right = dfs(root.right);
TreeNode left = dfs(root.left);
if(left != null){
left.right = root.right;
root.right = root.left;
root.left = null;
}
return right != null ? right : left != null ? left : root;
}
}
House Robber III
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police.
public class Solution {
/**
* @param root: The root of binary tree.
* @return: The maximum amount of money you can rob tonight
*/
public int houseRobber3(TreeNode root) {
// write your code here
if(root == null) return 0;
int[] ans = dfs(root);
return Math.max(ans[0], ans[1]);
}
//return [rob root, not rob root]
private int[] dfs(TreeNode root){
if(root == null) return new int[]{0, 0};
int[] left = dfs(root.left);
int[] right = dfs(root.right);
//如果抢root，则不能抢left或者right
int rob_root = left[1] + right[1] + root.val;
//如果不抢root，那么抢不抢left和right都可以，所以选最大值就行
int not_rob_root = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{rob_root, not_rob_root};
}
}
Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. Node.val can be negative.
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer
*/
public int maxPathSum(TreeNode root) {
// write your code here
if(root == null) return 0;
int[] path_sum = new int[1];
path_sum[0] = Integer.MIN_VALUE;
dfs(root, path_sum);
return path_sum[0];
}
//返回单边最长path的同时，更新path_summ
private int dfs(TreeNode root, int[] path_sum){
if(root == null) return 0;
int left_single_path = dfs(root.left, path_sum);
int right_single_path = dfs(root.right, path_sum);
//path_sum可以是双边的，path不能为空，所以不能为零
path_sum[0] = Math.max(path_sum[0], left_single_path + right_single_path + root.val);
//chain是单边的，可以为0，代表不取
return Math.max(Math.max(left_single_path , right_single_path) + root.val, 0);
}
}
Longest Path On The Tree
Given a tree consisting of n nodes, n-1 edges. Output the distance between the two nodes with the furthest distance on this tree. Given three arrays of size n-1, starts, ends, and lens, indicating that the i-th edge is from starts[i] to ends[i] and the length is lens[I].
Input：n=5, starts=[0,0,2,2], ends=[1,2,3,4], lens=[1,2,5,6]
Output：11
Explanation:
(3→2→4)the length of this path is 11, as well as(4→2→3)
class Pair{
int node;
int len;
public Pair(int node, int len){
this.node = node;
this.len = len;
}
}
public class Solution {
/**
* @param n: The number of nodes
* @param starts: One point of the edge
* @param ends: Another point of the edge
* @param lens: The length of the edge
* @return: Return the length of longest path on the tree.
*/
public int longestPath(int n, int[] starts, int[] ends, int[] lens) {
//第一次bfs，找到离root最远的点start以及其距离
//第二次bfs，找到离start最远的点end以及其距离
Map<Integer, List<Pair>> graph = new HashMap<>();
build_graph(n, starts, ends, lens, graph);
int[] start_len = bfs(starts[0], graph, n);
int[] end_len = bfs(start_len[0], graph, n);
return end_len[1];
}
private void build_graph(int n, int[] starts, int[] ends, int[] lens, Map<Integer, List<Pair>> graph ){
for(int i = 0; i < starts.length; i++){
if (!graph.containsKey(starts[i])){
graph.put(starts[i], new ArrayList<Pair>());
}
if (!graph.containsKey(ends[i])){
graph.put(ends[i], new ArrayList<Pair>());
}
graph.get(starts[i]).add(new Pair(ends[i], lens[i]));
graph.get(ends[i]).add(new Pair(starts[i], lens[i]));
}
}
//return farthest node and it's len from root;
private int[] bfs(int root, Map<Integer, List<Pair>> graph, int n){
Queue<Integer> q = new LinkedList<>();
int[] distance = new int[n];
Arrays.fill(distance, -1);
q.add(root);
distance[root] = 0;
int max_distance = 0;
int max_node = root;
while(!q.isEmpty()){
int parent = q.remove();
if(distance[parent] > max_distance){
max_distance = distance[parent];
max_node = parent;
}
for(Pair child : graph.get(parent)){
if(distance[child.node] != -1) continue;
distance[child.node] = distance[parent] + child.len;
q.add(child.node);
}
}
return new int[]{max_node, max_distance};
}
}
Traversal
Preorder Traversal
- Approach 1: Recursion
//running time: O(N)
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val=x;
}
}
class Solution{
List<Integer> ans=new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root){
if(root == null) return ans;
ans.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return ans;
}
}
- Approach 2: Iteration
//running time: O(N)
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if(root == null) {
return ans;
}
Stack<TreeNode> stack=new Stack<>();//也可以用linkedlist来implement
stack.push(root);
while(!stack.empty()) {
TreeNode curr=stack.pop();
ans.add(curr.val);
if(curr.right != null) {
stack.add(curr.right);//先放右子树，这样右子树会被后读
}
if(curr.left != null) {
stack.add(curr.left);//再放左子树，这样左子树会被先读
}
}
return ans;
}
}
Inorder Traversal
- Approach 1: Recursion
class Solution{
List<Integer> ans=new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root){
if(root == null) return ans;
inorderTraversal(root.left);
ans.add(root.val);
inorderTraversal(root.right);
return ans;
}
}
- Approach 2: Iteration
class Solution{
public List<Integer> inorderTraversal(TreeNode root){
List<Integer> ans=new ArrayList<>();
if(root == null){
return ans;
}
Stack<TreeNode> stack=new Stack<>();
TreeNode curr=root;
while(curr!=null || !stack.isEmpty()){
while(curr != null){
stack.push(curr);
curr=curr.left;
}
curr=stack.pop();
ans.add(curr.val);
curr=curr.right;//这里不用多余检查right child是不是null，外循环和内循环的条件会处理这种情况
}
return ans;
}
}
Postorder Traversal
- Approach 1: Recursion
class Solution {
List<Integer> ans=new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null) return ans;
postorderTraversal(root.left);
postorderTraversal(root.right);
ans.add(root.val);
return ans;
}
}
- Approach 2: Iteration
The order of postorder traversal:(left), (right), root.
The order of reverse postorder traversal: root, (right), (left).
The order of preorder traversal: root, (left), (right).
So we implement postorder traversal by reverse(rev_postorderTraversal()).
class Solution{
public List<Integer> postorderTraversal(TreeNode root){
LinkedList<Integer> ans=new LinkedList<>();
if(root == null) return ans;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode curr=stack.pop();
ans.addFirst(curr.val);//这里等于是在reverse ans
if(curr.left != null) stack.push(curr.left);
if(curr.right != null) stack.push(curr.right);
}
return ans;
}
}
Level order Traversal
Given [3, 9, 20, null, null, 15, 7], return [ [3], [9,20], [15,7] ]
- BFS
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans= new ArrayList<>();
if(root == null) return ans;
bfs(root,ans);
return ans;
}
private void bfs(TreeNode root,List<List<Integer>> ans){
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);// This method is used to add elements at the tail of queue.
while(!queue.isEmpty()){
int size=queue.size();
List<Integer> l =new ArrayList<>();
while(size>0){
TreeNode curr=queue.remove();//This method removes and returns the head of the queue
l.add(curr.val);
if(curr.left != null) queue.add(curr.left);
if(curr.right != null) queue.add(curr.right);
size--;
}
ans.add(l);
}
}
}
- DFS(pre-order)
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans =new ArrayList<>();
if(root==null) return ans;
dfs(root,0,ans);
return ans;
}
private void dfs(TreeNode root, int depth, List<List<Integer>> ans){
if(root==null) return;
while(ans.size()<=depth) ans.add(new ArrayList<Integer>());
ans.get(depth).add(root.val);//放这里就是preorder，放哪里不影响答案，因为root和child永远不在同一行，只要按照要求先访问left，再访问right就行
dfs(root.left,depth+1,ans);
dfs(root.right,depth+1,ans);
}
}
Construct Binary Tree
Construct Binary Tree from Preorder and Postorder Traversal
Given preorder and postorder traversal of a tree, construct the binary tree.(You may assume that duplicates do not exist in the tree). For example:
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
思路：
pre = [(root) (left) (right)]
post = [(left) (right) (root)]
这道题的关键是找到length of (left)。preorder顺序的第二个是root of left subtree（不用担心左子树为null的情况，因为在这里表示tree的形式，如果有一个subtree 为null，我们没办法判断是左边还是右，例如return[1,2,4,5]的话,[2,4,5]可以被认为是左子树或者右子树。而且题目说了If there exists multiple answers, you can return any of them.) 找到root of left subtree，例如2，在postorder里往前数就是length of (left)，这里是3. 然后recursively求解就行。
root = new TreeNode(1)
root.left = build((2,4,5), (4,5,2))
root.right = build((3,6,7), (6,7,3))
//O(N)
class Solution {
private int[] pre,post;
public TreeNode constructFromPrePost(int[] pre, int[] post) {
this.pre=pre;
this.post=post;
return build(0,0,pre.length);
}
private TreeNode build(int i, int j, int n){
//i j 是在pre和post里的起始位置，n是长度
if(n <= 0) return null;
TreeNode root = new TreeNode(pre[i]);
if(n == 1) return root;
int k=j; //k is the index of the root of the left subtree in post array
while(post[k] != pre[i+1]) k++; //pre[i+1] is the root of left subtree
int l=k-j+1; //l is the length of (left)
root.left=build(i+1,j,l);
root.right=build(i+l+1,k+1,n-l-1);
return root;
}
}
Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree. You may assume that duplicates do not exist in the tree. For example, given:
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
思路：
in=[(left) (root) (right)]
post = [(left) (right) (root)]
post的最后一个是root，在inorder里找到root的index，root左边全部是(left)，这样知道了length of (left)，这样可以通过postorder也找到(right)长度，recursively求解。
//该思路速度并不快，但是在interview是很容易想出来，思路也很清楚，无论给的是什么order
class Solution {
private int[] in,post;
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.in=inorder;
this.post=postorder;
return build(0,0,in.length);
}
private TreeNode build(int i, int j, int n){
if(n <= 0) return null;
TreeNode root = new TreeNode(post[j+n-1]);
if(n == 1) return root;
int k=i;
while(in[k] != post[j+n-1]) k++; //k is the index of root
int l = k-i; //l is the length of (left)
root.left=build(i,j,l);
root.right=build(i+l+1,j+l,n-l-1);
return root;
}
}
Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree. 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]
思路：
pre = [(root) (left) (right) ]
in=[(left) (root) (right)]
//O(N)
class Solution {
private int[] pre,in;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.pre=preorder;
this.in=inorder;
return build(0,0,preorder.length);
}
private TreeNode build(int i,int j, int n){
if(n <= 0) return null;
TreeNode root = new TreeNode(pre[i]);
if(n == 1) return root;
int k=j;
while(in[k] != pre[i]) k++;//k is the index of root in inorder array
int l = k-j;//l is the length of (left)
root.left=build(i+1,j,l);
root.right=build(i+l+1,k+1,n-l-1);
return root;
}
}
Serialize and Deserialize Binary Tree
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
//StringBuilder objects are like String objects, except that they can be modified
//这里我们需要像stringbuilder和queue这样可以被modified的object
StringBuilder sb= new StringBuilder();
helper(root,sb);
return sb.toString();
}
private void helper(TreeNode root, StringBuilder sb){
if(root == null) {
sb.append("#").append(" ");
}else{
sb.append(root.val).append(" "); //preorder
helper(root.left, sb);
helper(root.right,sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> q = new LinkedList<>();
q.addAll(Arrays.asList(data.split(" ")));
return deHelper(q);
}
private TreeNode deHelper(Queue<String> q){
String curr = q.remove();//remove from the head
if(curr.equals("#")) return null;
TreeNode root=new TreeNode(Integer.parseInt(curr));
root.left=deHelper(q);
root.right=deHelper(q);
return root;
}
}
Solve Problems Recursively
Maximum depth of a binary tree
Given a binary tree, find its maximum depth.
- "Top-down" Solution
"Top-down" means that in each recursive call, we will visit the node first to come up with some values, and pass these values to its children when calling the function recursively. So the "top-down" solution can be considered as a kind of preorder traversal.
class Solution {
private int ans=0;
public int maxDepth(TreeNode root) {
if(root==null) return ans;
dfs(root,1);
return ans;
}
private void dfs(TreeNode root, int depth){
if(root == null) return;
ans=Math.max(depth, ans); // it's like a kind of preorder traversal.
dfs(root.left, depth+1);
dfs(root.right, depth+1);
}
}
- "Bottom-up" Solution*
"Bottom-up" is another recursive solution. In each recursive call, we will firstly call the function recursively for all the children nodes and then come up with the answer according to the returned values and the value of the current node itself. This process can be regarded as a kind of postorder traversal.
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
int left_depth=maxDepth(root.left);
int right_depth=maxDepth(root.right);
return Math.max(left_depth,right_depth)+1;
}
}
Symmetric Tree
Given a binary tree, check whether it is a mirror of itself. A tree is symmetric if the left subtree is a mirror reflection of the right subtree:
-Their two roots have the same value.
-The right subtree of each tree is a mirror reflection of the left subtree of the other tree.
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return isMirror(root.left, root.right);
}
public boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);
}
}
