Interview question 27 — Mirror image of binary tree
Please complete a function, input a binary tree, the function output its mirror image.
In this chapter, it is suggested that when facing problems that cannot be solved temporarily, we should abstract out specific concepts by drawing pictures and giving examples, and analyze the problems clearly by giving examples (that is, summarizing and summarizing). In fact, image memory and induction and summary are also the best work of the human brain. When solving problems, making full use of the brain’s better ability to process is often twice the result with half the effort.
In this case, you can see that by recursively flipping the left and right of all the nodes.
public class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
switchLeftAndRight(root);
if(root.left ! =null) {
mirrorTree(root.left);
}
if(root.right ! =null) {
mirrorTree(root.right);
}
return root;
}
private void switchLeftAndRight(TreeNode root) {
if (root == null) {
return; } TreeNode temp = root.left; root.left = root.right; root.right = temp; }}Copy the codeInterview question 28 — Symmetric binary trees
Please implement a function to determine whether a binary tree is symmetric. A binary tree is symmetric if it is the same as its mirror image. For example, in the three binary trees shown in the figure, the first binary tree is actually symmetric, while the other two are not.
Val == root.right. Val) && isSymmetric(root.left, root.right)
A tree is a symmetric binary tree, that is, the left and right children of the root node have equal values and the left and right subtrees are symmetric
Now I need to define the symmetry of the two trees, isSymmetric(root1, root2) = (root1.val == root2.val) && isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left)
The two trees are symmetric, that is, the root nodes of the two trees are equal, and the left subtree of root1 is symmetric with the right subtree of root2, and the right subtree of root1 is symmetric with the left subtree of root2
public class Solution {
/* 1 / \ 2 2 / \ / \ 3 4 4 3 */
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return areSymmetric(root.left, root.right);
}
private boolean areSymmetric(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
} else if (root1 == null || root2 == null) {
return false;
}
returnroot1.val == root2.val && areSymmetric(root1.left, root2.right) && areSymmetric(root1.right, root2.left); }}Copy the codeInterview question 29 — Print the matrix clockwise
Enter a matrix and print out each number in clockwise order from the outside in. For example, if you enter the following matrix:
1,2,3, 4,5, 6, 7,8, 9, 10, 11,12, 13, 14,15,16 then print out the numbers 1,2,3,5,8,12,16,15…
The solution in the book is to break the clockwise rotation into n circles from the outside to the inside, and then traverse each circle.
The author’s method is to control the upper, lower, left and right boundaries until up>=down left>=right.
public class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return new int[0];
}
int[] result = new int[matrix.length * matrix[0].length];
int resultIndex = 0;
int i = 0;
int j = 0;
int up = 0;
int down = matrix.length;
int left = 0;
int right = matrix[0].length;
while(up < down && left < right) {
while(j < right) {
result[resultIndex++] = matrix[i][j];
j++;
}
j--;
up++;
i++;
if (up >= down || left >= right) {
break;
}
while(i < down) {
result[resultIndex++] = matrix[i][j];
i++;
}
i--;
right--;
j--;
if (up >= down || left >= right) {
break;
}
while(j >= left) {
result[resultIndex++] = matrix[i][j];
j--;
}
j++;
down--;
i--;
if (up >= down || left >= right) {
break;
}
while(i >= up) {
result[resultIndex++] = matrix[i][j];
i--;
}
i++;
left++;
j++;
}
returnresult; }}Copy the codeInterview question 30 — Stacks containing min functions
Define the data structure of the stack, please implement a min function in this type that can get the smallest element of the stack. In this stack, the time complexity of min, push, and POP calls is O(1)
Because the time complexity of the min function is O(1), it takes O(n) time to remove the smallest element from the stack in the traditional stack structure storage mode. Therefore, it is necessary to expand the internal storage structure of the stack, that is, to add an internal stack of the smallest element, as shown in the figure below.
The push process is as follows:
The process of POP is as follows:
Based on the above analysis, the implementation code can be obtained:
public class MinStack {
private Deque<Integer> dataStack;
private Deque<Integer> minDataStack;
/** initialize your data structure here. */
public MinStack(a) {
dataStack = new LinkedList<>();
minDataStack = new LinkedList<>();
}
public void push(int x) {
dataStack.push(x);
if(minDataStack.isEmpty() || x <= minDataStack.peek()) { minDataStack.push(x); }}public void pop(a) {
int data = dataStack.pop();
if(data == minDataStack.peek()) { minDataStack.pop(); }}public int top(a) {
return dataStack.peek();
}
public int min(a) {
returnminDataStack.peek(); }}Copy the codeInterview question 31 — Push and pop sequences on stacks
Input two sequences of integers. The first sequence indicates the order in which the stack is pushed. Please determine whether the second sequence is the eject order of the stack. Assume that all the numbers pushed are not equal. For example, the sequence {1,2,3,4,5} is a pushdown sequence of a stack, and the sequence {4,5,3,2,1} is a corresponding pop-up sequence of the pushdown sequence, but {4,3,5,1,2} cannot be a pushdown sequence of the pushdown sequence.
The straightforward solution to this problem is to simulate the push and eject of the stack in terms of the sequence, returning false if the operation is obviously undoable, and true if it is complete otherwise. The process is shown as follows:
Interview question 32 — Print binary trees from top to bottom
Topic 1: Print a binary tree from top to bottom
Each node of the binary tree is printed from top to bottom, and nodes of the same level are printed from left to right. For example, enter the binary tree shown below and print 8,6,10,5,7,8,11 all at once
The basic level traversal, the title one will not repeat.
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
List<Integer> result = new LinkedList<>();
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(! queue.isEmpty()) { TreeNode node = queue.poll(); result.add(node.val);if(node.left ! =null) {
queue.offer(node.left);
}
if(node.right ! =null) { queue.offer(node.right); }}int[] array = new int[result.size()];
int i = 0;
for (Integer val : result) {
array[i++] = val;
}
return array;
}
Copy the codeTitle two: Branch prints binary trees from top to bottom
The binary tree is printed from top to bottom layer, with nodes of the same layer printed from left to right, each layer printed to a row. For example, the binary tree in the figure above yields:
8, 6, 10, 5, 7, 9, 11
Unlike base level traversal, you need to focus on the current level while traversing. The first idea I came up with was to extend an object <Node, currentLevel>, traverse the base level, and print a newline when level first increases.
Another simpler way is in the book on the basis of the basic level traversal, add a temporary queue, ensure that only the current level of node in the queue, will these nodes around the child to another new temporary queue, after processing the current queue print newlines and temporary queue switch and the current reference queue, continue on to the next layer traversal.
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(! queue.isEmpty()) { Queue<TreeNode> newQueue =new LinkedList<>();
List<Integer> line = new ArrayList<>();
while(! queue.isEmpty()) { TreeNode node = queue.poll(); line.add(node.val);if(node.left ! =null) {
newQueue.offer(node.left);
}
if(node.right ! =null) {
newQueue.offer(node.right);
}
}
result.add(line);
queue = newQueue;
}
return result;
}
Copy the codeA more ingenious method is provided in Leetcode. After each layer of here is processed, the size of the current queue is the number of nodes contained in the current layer. Therefore, it is necessary to iterate after consuming the size elements, print a newline, and then continue to record the new size to continue the iterate. Specific can refer to the practice of links, no longer repeat the drawing.
public List<List<Integer>> levelOrderFasterVersion(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(! queue.isEmpty()) { List<Integer> line =new ArrayList<>();
for (int i = queue.size(); i > 0; i--) { // The current queue.size() is the number of nodes in this layer, which only controls the number of queue.poll
TreeNode node = queue.poll();
line.add(node.val);
if(node.left ! =null) queue.offer(node.left);
if(node.right ! =null) queue.offer(node.right);
}
result.add(line);
}
return result;
}
Copy the codeTopic 3: Zigzag printing binary trees
Implement a function to print the binary tree in glyph order, that is, the first line is printed from left to right, the second line is printed from right to left, the third line is printed from left to right, and so on. For example, the result of the binary tree in the figure is:
1
3 2
4 5 6 7
15 14 13 12 11 10 9 8
To expand on question two,
- Add a bool variable to Reverted
- Poll from the end of the queue or poll from the head of the queue, depending on the Reverted.
- After each layer is traversed, reverted determines whether to queue left to right or right to left
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
Deque<TreeNode> queue = new LinkedList<>();
queue.offerLast(root);
boolean reverted = false;
while(! queue.isEmpty()) { List<Integer> line =new ArrayList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode node = reverted ? queue.pollLast() : queue.pollFirst();
line.add(node.val);
if(! reverted) {if(node.left ! =null) queue.offerLast(node.left);
if(node.right ! =null) queue.offerLast(node.right);
} else {
if(node.right ! =null) queue.offerFirst(node.right);
if(node.left ! =null) queue.offerFirst(node.left); } } reverted = ! reverted; result.add(line); }return result;
}
Copy the codeInterview question 33 — Backward traversal sequence of binary search trees
Enter an array of integers and determine if the array is the result of subsequent traversal of a binary search tree. Returns true if it is, false otherwise. Suppose any two numbers in the input array are different. For example, entering the array {5,7,6,9,11,10,8} returns true because the sequence of integers is the result of subsequent traversal of the binary search tree shown in the figure. If the input array is {7,4,6,5}, then false is returned because no subsequent traversal of the binary tree results in this sequence.
Binary search trees are characterized by the left child being smaller than the root and the right child being larger than the root. The characteristic of the subsequent traversal is that the last node is the root node, the first half of the remaining part is divided into the left subtree, and the right part is the right subtree, as shown in the following figure:
Based on the above analysis, the judgment logic of the order traversal sequence behind the binary search tree can be obtained as follows:
- If the length of the sequence is 1, only one element of the sequence must be, return true (also recursive exit)
- The last value of the sequence is root,
- If we traverse the sequence until we see the first number greater than root, we are at the far right of the left. Then we need to determine whether the rest of the sequence is greater than root
- Return false if the right subtree nodes are not all greater than root, which is not a correct binary search tree traversal sequence
- If all the right subtrees are larger than root, then the right and left subtrees are recursively judged to be the correct sequence of binary search tree
public boolean verifyPostorder(int[] postorder) {
if(postorder == null || postorder.length == 0) {
return true;
}
return verifyPostorderCore(postorder, 0, postorder.length);
}
private boolean verifyPostorderCore(int[] postorder, int start, int end) {
if (start >= end || end - start == 1) {
return true;
}
int firstOfRight = findFirstOfRight(postorder, start, end);
return allBiggerThanRoot(postorder, firstOfRight, end)
&& verifyPostorderCore(postorder, start, firstOfRight)
&& verifyPostorderCore(postorder, firstOfRight, end - 1);
}
private int findFirstOfRight(int[] postorder, int start, int end) {
int root = postorder[end-1];
for(int i = start; i < end; i++) {
if(postorder[i] > root) {
returni; }}return end-1;
}
private boolean allBiggerThanRoot(int[] postorder, int start, int end) {
int root = postorder[end-1];
for(int i = start; i < end; i++) {
if(postorder[i] < root) {
return false; }}return true;
}
Copy the codeInterview question 34 — Binary tree neutral path to a certain value
Input a binary tree and an integer. Print out the sum of the node values in the binary tree as all paths to the input integers. A path is formed from the root of the tree down to the nodes passed by the leaf.
This problem can be solved by the conventional DFS backtracking method, by recursively going down to the leaf node, accumulating the sum of nodes on the path, comparing target, and adding the result set if they are equal. If not, return directly. Go back to the previous layer and remove the last element.
public List<List<Integer>> pathSum(TreeNode root, int target) {
List<List<Integer>> result = new ArrayList<>();
pathSumCore(root, target, 0.new ArrayList<>(), result);
return result;
}
private void pathSumCore(TreeNode root, int target, int sum, List<Integer> temp, List<List<Integer>> result) {
if (root == null) {
return;
}
sum += root.val;
temp.add(root.val);
if (root.left == null && root.right == null) { // it's a leaf node
if (sum == target) {
result.add(new ArrayList<>(temp));
}
return;
}
if(root.left ! =null) {
pathSumCore(root.left, target, sum, temp, result);
temp.remove(temp.size() - 1);
}
if(root.right ! =null) {
pathSumCore(root.right, target, sum, temp, result);
temp.remove(temp.size() - 1); }}Copy the codeInterview question 35 — Replication of complex linked lists
Please implement the function to copy a complex linked list. In complex linked lists, each node has a next pointer to the next node and a random pointer to any node in the list, or null.
Time complexity O(n^2), space complexity O(1)
There are many solutions to this problem, but the most time-intensive solution is to copy the nodes along next and then copy the
Time complexity O(n), space complexity O(n) but requires an additional hash space method
Using the hash table to record the mapping of the original node -> replicated node,
- If no mapping exists, create a replication node and create a mapping
- If there is mapping, read the corresponding replication node from the Hash table and set the pointer
public Node copyRandomList(Node head) {
Map<Node, Node> nodeMap = new HashMap<>();
Node originNode = head;
Node resultHead = new Node(0);
Node copyNode = resultHead;
while(originNode ! =null) {
copyNode.next = copyOrFindNode(originNode, nodeMap);
copyNode.next.random = copyOrFindNode(originNode.random, nodeMap);
copyNode = copyNode.next;
originNode = originNode.next;
}
return resultHead.next;
}
private Node copyOrFindNode(Node originNode, Map<Node, Node> nodeMap) {
if (originNode == null) {
return null;
}
if(nodeMap.get(originNode) ! =null) {
return nodeMap.get(originNode);
}
Node copyNode = new Node(originNode.val);
nodeMap.put(originNode, copyNode);
return copyNode;
}
Copy the codeTime complexity O(n), space complexity O(n) but do not need the method of auxiliary space
The book offers a solution that doesn’t require auxiliary space:
- Insert a copy of each node in the original linked list after that node, as shown below
- Then, the random pointer of each original node points to a node whose random copy node points to the random node after that of the original node (i.e., the copy node of random).
- Separate the original node from the replica node
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
copyNodeToNeighbor(head); / / 1
copyRandom(head); / / 2
return extractCopyList(head); / / 3
}
private void copyNodeToNeighbor(Node head) {
Node originNode = head;
while(originNode ! =null) {
Node nextNode = originNode.next;
originNode.next = newNode(originNode.val); originNode.next.next = nextNode; originNode = nextNode; }}private void copyRandom(Node head) {
Node originNode = head;
Node copyNode = head.next;
while(originNode ! =null) {
if(originNode.random ! =null) {
copyNode.random = originNode.random.next;
}
if (copyNode.next == null) {
break; } originNode = originNode.next.next; copyNode = copyNode.next.next; }}private Node extractCopyList(Node head) {
Node originHead = head;
Node originNode = originHead;
Node copyHead = head.next;
Node copyNode = copyHead;
while(originNode.next.next ! =null) {
originNode.next = originNode.next.next;
originNode = originNode.next;
copyNode.next = copyNode.next.next;
copyNode = copyNode.next;
}
originNode.next = null;
return copyHead;
}
Copy the codeInterview question 36 — Binary search trees and bidirectional linked lists
Title: Input a binary search tree and convert the binary search tree into a sorted bidirectional linked list. You cannot create any new nodes. You can only adjust the Pointers to nodes in the tree. For example, enter the binary search tree on the left of the figure and output the transformed sorted bidirectional linked list.
The arrangement of binary search tree from small to large is exactly the middle order traversal result of the binary tree, so we only need to process the left and right Pointers of nodes in the middle order traversal process and sew them into a bidirectional linked list.
For example, when traversing to 10, what we need to do is to connect the last (i.e., the largest) node in the left subtree with the current node, and return the current largest node (i.e., 10 nodes) for the right subtree to connect. The whole process is expressed in words as follows:
- Transform left tree to Double List transform left tree to Double list
- Join the last node of the left tree with the current node.
- Transform right tree to Double List transform right tree to Double List
class Solution {
private Node pre;
private Node head;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
dfs(root);
head.left = pre; // In leetcode, you need to connect the head and last nodes to make a circular list
pre.right = head;
return head;
}
private void dfs(Node node) {
if (node == null) {
return;
}
dfs(node.left);
if (pre == null) {
head = node;
} else{ node.left = pre; pre.right = node; } pre = node; dfs(node.right); }}Copy the codeInterview question 37 — Serialize binary trees
Implement two functions to serialize and deserialize the binary tree
Serialization: Use hierarchical traversal and write NULL for empty nodes
Deserialization: By looking at the serialized string, we can see that the left and right children of each node are after the current read position, as in:
- The children around 1 are 2, 3, and index goes to 3
- The index goes to 5
- The kids around 3 are 5, 6, and index goes to 7.
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
List<String> resultList = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(! queue.isEmpty()) { TreeNode node = queue.poll();if (node == null) {
resultList.add("null");
} else {
resultList.add(node.val + ""); queue.offer(node.left); queue.offer(node.right); }}return listToString(resultList);
}
private String listToString(List<String> list) {
StringBuilder builder = new StringBuilder();
builder.append("[");
for (String num : list) {
builder.append(num).append(",");
}
builder.deleteCharAt(builder.length() - 1);
builder.append("]");
return builder.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String trimmedData = data.substring(1, data.length() - 1);
String[] nums = trimmedData.split(",");
TreeNode root = generateTreeNode(nums[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int index = 1;
while(! queue.isEmpty()) { TreeNode node = queue.poll(); node.left = generateTreeNode(nums[index]);if(node.left ! =null) {
queue.offer(node.left);
}
node.right = generateTreeNode(nums[index + 1]);
if(node.right ! =null) {
queue.offer(node.right);
}
index += 2;
}
return root;
}
private TreeNode generateTreeNode(String num) {
if (num == null || "null".equals(num)) {
return null;
}
return new TreeNode(Integer.parseInt(num));
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(intx) { val = x; }}}Copy the codeInterview question 38 — Arrangement of strings
Enter a string and print out all permutations of the characters in the string. For example, if you enter the string ABC, you print out all the strings ABC, ACb, BAC, BCA, CAB, and CBA that can be arranged by characters A, B, and C.
This topic is the complete permutation problem, taking ABC as an example
- First swap a and A (TP in place), or ABC
- And then switch the second position b and b, again ABC
- Finally swap the third position c and C –> ABC
- And then switch the second position b and c is equal to acb
- Finally swap the third position B and B –> ACb
- And then switch the second position b and b, again ABC
- So let’s switch a and B equals bac
- Then switch the second position, A, and a = bac
- Finally swap the third position c and C –> BAC
.
- Then switch the second position, A, and a = bac
Each layer of DFS swaps one bit with all the following bits
class Solution {
private Set<String> result = new HashSet<>();
public String[] permutation(String s) {
if (s == null || s.length() == 0) {
return new String[0];
}
permutationCore(s.toCharArray(), 0."");
return result.toArray(new String[0]);
}
private void permutationCore(char[] s, int cur, String temp) {
if (cur == s.length - 1) {
result.add(temp + s[cur]);
return;
}
for (int i = cur; i < s.length; i++) {
swap(s, i, cur);
permutationCore(s, cur+1, temp+s[cur]); swap(s, i, cur); }}private void swap(char[] s, int i, int j) {
chartemp = s[i]; s[i] = s[j]; s[j] = temp; }}Copy the code