3.树&堆
这里的树通常是指二叉树。
|
1
2
3
4
5
|
class TreeNode{ int value; TreeNode left; TreeNode right;} |
下面是一些与二叉树有关的概念：
- 二叉树搜索：对于所有节点，顺序是：left children <= current node <= right children；
- 平衡vs.非平衡：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树；
- 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点；
- 完美二叉树（Perfect Binary Tree）：一个满二叉树，所有叶子都在同一个深度或同一级，并且每个父节点都有两个子节点；
- 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
堆（Heap）是一个基于树的数据结构，也可以称为优先队列（ PriorityQueue），在队列中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
下面列出一些基于二叉树和堆的算法：
二叉树前序遍历
Preorder binary tree traversal is a classic interview problem about trees. The key to solve this problem is to understand the following:
- What is preorder? (parent node is processed before its children)
- Use Stack from Java Core library
It is not obvious what preorder for some strange cases. However, if you draw a stack and manually execute the program, how each element is pushed and popped is obvious.
The key to solve this problem is using a stack to store left and right children, and push right child first so that it is processed after the left child.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> returnList = new ArrayList<Integer>();
if(root == null)
return returnList;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.empty()){
TreeNode n = stack.pop();
returnList.add(n.val);
if(n.right != null){
stack.push(n.right);
}
if(n.left != null){
stack.push(n.left);
}
}
return returnList;
}
}
二叉树中序遍历
The key to solve inorder traversal of binary tree includes the following:
- The order of “inorder” is: left child -> parent -> right child
- Use a stack to track nodes
- Understand when to push node into the stack and when to pop node out of the stack
//Definition for binary tree
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public ArrayList<Integer> inorderTraversal(TreeNode root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ArrayList<Integer> lst = new ArrayList<Integer>();
if(root == null)
return lst;
Stack<TreeNode> stack = new Stack<TreeNode>();
//define a pointer to track nodes
TreeNode p = root;
while(!stack.empty() || p != null){
// if it is not null, push to stack
//and go down the tree to left
if(p != null){
stack.push(p);
p = p.left;
// if no left child
// pop stack, process the node
// then let p point to the right
}else{
TreeNode t = stack.pop();
lst.add(t.val);
p = t.right;
}
}
return lst;
}
}
二叉树后序遍历
The key to to iterative postorder traversal is the following:
- The order of “Postorder” is: left child -> right child -> parent node.
- Find the relation between the previously visited node and the current node
- Use a stack to track nodes
As we go down the tree, check the previously visited node. If it is the parent of the current node, we should add current node to stack. When there is no children for current node, pop it from stack. Then the previous node become to be under the current node for next loop.
//Definition for binary tree public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> lst = new ArrayList<Integer>(); if(root == null) return lst; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); TreeNode prev = null; while(!stack.empty()){ TreeNode curr = stack.peek(); // go down the tree. //check if current node is leaf, if so, process it and pop stack, //otherwise, keep going down if(prev == null || prev.left == curr || prev.right == curr){ //prev == null is the situation for the root node if(curr.left != null){ stack.push(curr.left); }else if(curr.right != null){ stack.push(curr.right); }else{ stack.pop(); lst.add(curr.val); } //go up the tree from left node //need to check if there is a right child //if yes, push it to stack //otherwise, process parent and pop stack }else if(curr.left == prev){ if(curr.right != null){ stack.push(curr.right); }else{ stack.pop(); lst.add(curr.val); } //go up the tree from right node //after coming back from right node, process parent node and pop stack. }else if(curr.right == prev){ stack.pop(); lst.add(curr.val); } prev = curr; } return lst; } }
字梯
The problem:
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
This problem is a classic problem that has been asked frequently during interviews. The following are two Java solutions.
1. Naive Approach
In a simplest way, we can start from start word, change one character each time, if it is in the dictionary, we continue with the replaced word, until start == end.
public class Solution {
public int ladderLength(String start, String end, HashSet<String> dict) {
int len=0;
HashSet<String> visited = new HashSet<String>();
for(int i=0; i<start.length(); i++){
char[] startArr = start.toCharArray();
for(char c='a'; c<='z'; c++){
if(c==start.toCharArray()[i]){
continue;
}
startArr[i] = c;
String temp = new String(startArr);
if(dict.contains(temp)){
len++;
start = temp;
if(temp.equals(end)){
return len;
}
}
}
}
return len;
}
}
|
Apparently, this is not good enough. The following example exactly shows the problem. It can not find optimal path. The output is 3, but it actually only takes 2.
Input: "a", "c", ["a","b","c"]
Output: 3
Expected: 2
2. Breath First Search
So we quickly realize that this looks like a tree searching problem for which breath first guarantees the optimal solution.
Assuming we have all English words in the dictionary, and the start is “hit” as shown in the diagram below.
We can use two queues to traverse the tree, one stores the nodes, the other stores the step numbers. Before starting coding, we can visualize a tree in mind and come up with the following solution.
public class Solution {
public int ladderLength(String start, String end, HashSet<String> dict) {
if (dict.size() == 0)
return 0;
LinkedList<String> wordQueue = new LinkedList<String>();
LinkedList<Integer> distanceQueue = new LinkedList<Integer>();
wordQueue.add(start);
distanceQueue.add(1);
while(!wordQueue.isEmpty()){
String currWord = wordQueue.pop();
Integer currDistance = distanceQueue.pop();
if(currWord.equals(end)){
return currDistance;
}
for(int i=0; i<currWord.length(); i++){
char[] currCharArr = currWord.toCharArray();
for(char c='a'; c<='z'; c++){
currCharArr[i] = c;
String newWord = new String(currCharArr);
if(dict.contains(newWord)){
wordQueue.add(newWord);
distanceQueue.add(currDistance+1);
dict.remove(newWord);
}
}
}
}
return 0;
}
}
3. What learned from this problem?
- Use breath-first or depth-first search to solve problems
- Use two queues, one for words and another for counting
验证二叉查找树
Problem:
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.
Thoughts about This Problem
All values on the left sub tree must be less than root, and all values on the right sub tree must be greater than root.
Java Solution
// Definition for binary tree
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public static boolean isValidBST(TreeNode root) {
return validate(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public static boolean validate(TreeNode root, int min, int max) {
if (root == null) {
return true;
}
// not in range
if (root.val <= min || root.val >= max) {
return false;
}
// left subtree must be < root.val && right subtree must be > root.val
return validate(root.left, min, root.val) && validate(root.right, root.val, max);
}
}
把二叉树变平放到链表里
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/
2 5
/
3 4 6
The flattened tree should look like:
1
2
3
4
5
6
Thoughts
Go down through the left, when right is not null, push right to stack.
Java Solution
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public void flatten(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while(p != null || !stack.empty()){
if(p.right != null){
stack.push(p.right);
}
if(p.left != null){
p.right = p.left;
p.left = null;
}else if(!stack.empty()){
TreeNode temp = stack.pop();
p.right=temp;
}
p = p.right;
}
}
}
|
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/
4 8
/ /
11 13 4
/
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
Thoughts
Add all node to a queue and store sum value of each node to another queue. When it is a leaf node, check the stored sum value.
For example above, the queue would be: 5 – 4 – 8 – 11 – 13 – 4 – 7 – 2 – 1. It will check node 13, 7, 2 and 1.
This is a typical breadth first search(BFS) problem.
Java Solution
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; LinkedList<TreeNode> nodes = new LinkedList<TreeNode>(); LinkedList<Integer> values = new LinkedList<Integer>(); nodes.add(root); values.add(root.val); while(!nodes.isEmpty()){ TreeNode curr = nodes.poll(); int sumValue = values.poll(); if(curr.left == null && curr.right == null && sumValue==sum){ return true; } if(curr.left != null){ nodes.add(curr.left); values.add(sumValue+curr.left.val); } if(curr.right != null){ nodes.add(curr.right); values.add(sumValue+curr.right.val); } } return false; } }
从前序和后序构建二叉树
Throughts
This problem can be illustrated by using a simple example.
in-order: 4 2 5 (1) 6 7 3 8
post-order: 4 5 2 6 7 8 3 (1)
From the post-order array, we know that last element is the root. We can find the root in in-order array. Then we can identify the left and right sub-trees of the root from in-order array.
Using the length of left sub-tree, we can identify left and right sub-trees in post-order array. Recursively, we can build up the tree.
Java Solution
//Definition for binary tree
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
int inStart = 0;
int inEnd = inorder.length-1;
int postStart =0;
int postEnd = postorder.length-1;
return buildTree(inorder, inStart, inEnd, postorder, postStart, postEnd);
}
public TreeNode buildTree(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd){
if(inStart > inEnd || postStart > postEnd)
return null;
int rootValue = postorder[postEnd];
TreeNode root = new TreeNode(rootValue);
int k=0;
for(int i=0; i< inorder.length; i++){
if(inorder[i]==rootValue){
k = i;
break;
}
}
root.left = buildTree(inorder, inStart, k-1, postorder, postStart, postStart+k-(inStart+1));
// Becuase k is not the length, it it need to -(inStart+1) to get the length
root.right = buildTree(inorder, k+1, inEnd, postorder, postStart+k-inStart, postEnd-1);
// postStart+k-inStart = postStart+k-(inStart+1) +1
return root;
}
}
|
把有序数组转换为二叉查找树
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Thoughts
Straightforward! Recursively do the job.
Java Solution
// Definition for binary tree
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode sortedArrayToBST(int[] num) {
if (num.length == 0)
return null;
return sortedArrayToBST(num, 0, num.length - 1);
}
public TreeNode sortedArrayToBST(int[] num, int start, int end) {
if (start > end)
return null;
int mid = (start + end) / 2;
TreeNode root = new TreeNode(num[mid]);
root.left = sortedArrayToBST(num, start, mid - 1);
root.right = sortedArrayToBST(num, mid + 1, end);
return root;
}
}
|
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Thoughts
If you are given an array, the problem is quite straightforward. But things get a little more complicated when you have a singly linked list instead of an array. Now you no longer have random access to an element in O(1) time. Therefore, you need to create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order at the same time as creating nodes.
Java Solution
// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
// Definition for binary tree
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
static ListNode h;
public TreeNode sortedListToBST(ListNode head) {
if (head == null)
return null;
h = head;
int len = getLength(head);
return sortedListToBST(0, len - 1);
}
// get list length
public int getLength(ListNode head) {
int len = 0;
ListNode p = head;
while (p != null) {
len++;
p = p.next;
}
return len;
}
// build tree bottom-up
public TreeNode sortedListToBST(int start, int end) {
if (start > end)
return null;
// mid
int mid = (start + end) / 2;
TreeNode left = sortedListToBST(start, mid - 1);
TreeNode root = new TreeNode(h.val);
h = h.next;
TreeNode right = sortedListToBST(mid + 1, end);
root.left = left;
root.right = right;
return root;
}
}
最小深度二叉树
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Thoughts
Need to know LinkedList is a queue. add() and remove() are the two methods to manipulate the queue.
Java Solution
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
LinkedList<Integer> counts = new LinkedList<Integer>();
nodes.add(root);
counts.add(1);
while(!nodes.isEmpty()){
TreeNode curr = nodes.remove();
int count = counts.remove();
if(curr.left != null){
nodes.add(curr.left);
counts.add(count+1);
}
if(curr.right != null){
nodes.add(curr.right);
counts.add(count+1);
}
if(curr.left == null && curr.right == null){
return count;
}
}
return 0;
}
}
|
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/
2 3
Return 6.
Thoughts
1) Recursively solve this problem
2) Get largest left sum and right sum
2) Compare to the stored maximum
Java Solution 1
// Definition for binary tree
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
//store max value
int max;
public int maxPathSum(TreeNode root) {
max = (root == null) ? 0 : root.val;
findMax(root);
return max;
}
public int findMax(TreeNode node) {
if (node == null)
return 0;
// recursively get sum of left and right path
int left = Math.max(findMax(node.left), 0);
int right = Math.max(findMax(node.right), 0);
//update maximum here
max = Math.max(node.val + left + right, max);
// return sum of largest path of current node
return node.val + Math.max(left, right);
}
}
|
Java Solution 2
We can also use an array to store value for recursive methods.
public class Solution {
public int maxPathSum(TreeNode root) {
int max[] = new int[1];
max[0] = Integer.MIN_VALUE;
calculateSum(root, max);
return max[0];
}
public int calculateSum(TreeNode root, int[] max) {
if (root == null)
return 0;
int left = calculateSum(root.left, max);
int right = calculateSum(root.right, max);
int current = Math.max(root.val, Math.max(root.val + left, root.val + right));
max[0] = Math.max(max[0], Math.max(current, left + root.val + right));
return current;
}
}
平衡二叉树
Given a binary tree, determine if it is height-balanced.
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.
Thoughts
A typical recursive problem for solving tree problems.
Java Solution
// Definition for binary tree
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
if (getHeight(root) == -1)
return false;
return true;
}
public int getHeight(TreeNode root) {
if (root == null)
return 0;
int left = getHeight(root.left);
int right = getHeight(root.right);
if (left == -1 || right == -1)
return -1;
if (Math.abs(left - right) > 1) {
return -1;
}
return Math.max(left, right) + 1;
}
}
4.Graph
与Graph相关的问题主要集中在深度优先搜索和宽度优先搜索。深度优先搜索非常简单，你可以从根节点开始循环整个邻居节点。下面是一个非常简单的宽度优先搜索例子，核心是用队列去存储节点。
第一步，定义一个GraphNode
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class GraphNode{ int val; GraphNode next; GraphNode[] neighbors; boolean visited; GraphNode(int x) { val = x; } GraphNode(int x, GraphNode[] n){ val = x; neighbors = n; } public String toString(){ return "value: "+ this.val; }} |
第二步，定义一个队列
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Queue{ GraphNode first, last; public void enqueue(GraphNode n){ if(first == null){ first = n; last = first; }else{ last.next = n; last = n; } } public GraphNode dequeue(){ if(first == null){ return null; }else{ GraphNode temp = new GraphNode(first.val, first.neighbors); first = first.next; return temp; } }} |
第三步，使用队列进行宽度优先搜索
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
public class GraphTest { public static void main(String[] args) { GraphNode n1 = new GraphNode(1); GraphNode n2 = new GraphNode(2); GraphNode n3 = new GraphNode(3); GraphNode n4 = new GraphNode(4); GraphNode n5 = new GraphNode(5); n1.neighbors = new GraphNode[]{n2,n3,n5}; n2.neighbors = new GraphNode[]{n1,n4}; n3.neighbors = new GraphNode[]{n1,n4,n5}; n4.neighbors = new GraphNode[]{n2,n3,n5}; n5.neighbors = new GraphNode[]{n1,n3,n4}; breathFirstSearch(n1, 5); } public static void breathFirstSearch(GraphNode root, int x){ if(root.val == x) System.out.println("find in root"); Queue queue = new Queue(); root.visited = true; queue.enqueue(root); while(queue.first != null){ GraphNode c = (GraphNode) queue.dequeue(); for(GraphNode n: c.neighbors){ if(!n.visited){ System.out.print(n + " "); n.visited = true; if(n.val == x) System.out.println("Find "+n); queue.enqueue(n); } } } }} |
输出结果：
|
1
2
|
value: 2 value: 3 value: 5 Find value: 5value: 4 |
实际中，基于Graph需要经常用到的算法：
克隆Graph
LeetCode Problem:
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
Key to Solve This Problem
- A queue is used to do breath first traversal.
- a map is used to store the visited nodes. It is the map between original node and copied node.
It would be helpful if you draw a diagram and visualize the problem.
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null)
return null;
LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
HashMap<UndirectedGraphNode, UndirectedGraphNode> map =
new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
UndirectedGraphNode newHead = new UndirectedGraphNode(node.label);
queue.add(node);
map.put(node, newHead);
while(!queue.isEmpty()){
UndirectedGraphNode curr = queue.pop();
ArrayList<UndirectedGraphNode> currNeighbors = curr.neighbors;
for(UndirectedGraphNode aNeighbor: currNeighbors){
if(!map.containsKey(aNeighbor)){
UndirectedGraphNode copy = new UndirectedGraphNode(aNeighbor.label);
map.put(aNeighbor,copy);
map.get(curr).neighbors.add(copy);
queue.add(aNeighbor);
}else{
map.get(curr).neighbors.add(map.get(aNeighbor));
}
}
}
return newHead;
}
}