[Sword Refers to offer] Concrete Abstract Problems

1. Stack containing min function

To define the data structure of the stack, please implement a min function (time complexity should be O(1)) in this type that can obtain the minimum elements contained in the stack.

Train of thought

1. Define two stacks, one stack is used to store data and the other stack is used to store the minimum value of the stack each time data is pushed into the stack.

2. Each time data is pushed into the stack, the data is compared with the top element of the minimum stack, and the smaller value compared between the two is stored into the minimum stack again.

4. The data stack is pushed out, and the minimum stack is pushed out.

3. The top of the minimum stack is always the minimum of the current stack.

Code

var dataStack = [];
 var minStack = [];
 
 function push(node)
 {
 dataStack.push(node);
 if(minStack.length === 0 ||  node < min()){
 minStack.push(node);
 }else{
 minStack.push(min());
 }
 }
 function pop()
 {
 minStack.pop();
 return dataStack.pop();
 }
 function top()
 {
 var length = dataStack.length;
 return length>0&&dataStack[length-1]
 }
 function min()
 {
 var length = minStack.length;
 return length>0&&minStack[length-1]
 }

2. Stack push-in and pop-out sequences

Enter two integer sequences. The first sequence represents the push-in order of the stack. Please judge whether the second sequence is likely to be the pop-up order of the stack. Suppose all the numbers pushed into the stack are not equal. For example, sequence 1,2,3,4,5 is the push-in sequence of a stack, sequence 4,5,3,2,1 is a pop-up sequence corresponding to the push-in sequence, but 4,3,5,1,2 cannot be the pop-up sequence of the push-in sequence. (Note: The lengths of these two sequences are equal)

Train of thought

1. Use an auxiliary stack to store data.

2. Stack the data in pushV in turn.

3. It is possible to push the stack after any push. When the push data is no longer at the top of the stack, push the stack.

4. Therefore, an index is set to record the current stack position, and the stack index is +1 each time.

5. When all data are stacked, if the stacking order is correct, the auxiliary stack should be empty.

Code

function IsPopOrder(pushV, popV) {
if (!  pushV || !  popV || pushV.length == 0 || popV.length == 0) {
return;
}
var stack = [];
var idx = 0;
for (var i = 0;   i < pushV.length;  i++) {
stack.push(pushV[i]);
while (stack.length && stack[stack.length - 1] == popV[idx]) {
stack.pop();
idx++;
}
}
return stack.length == 0;
}

3. Follow-up traversal of binary tree

Enter an integer array to determine whether the array is the result of a subsequent traversal of a binary search tree. If Yes, output yes, otherwise output no. Assume that any two numbers of the input array are different from each other.

Train of thought

1. Postorder traversal: It is divided into three parts: the last node is the heel node, the second part is that the value of the left subtree is smaller than that of the heel node, and the third part is that the value of the right subtree is larger than that of the heel node.

2. First, the left subtree is detected. The left subtree is determined as the value smaller than the heel node.

3. Other values except the last node and the left subtree are the right subtree. If one of the right subtrees is smaller than the heel node, false is returned.

4. If there are left and right subtrees, recursively detect whether the left and right subtrees are composite specifications.

Code

function VerifySquenceOfBST(sequence) {
 if (sequence && sequence.length > 0) {
 var root = sequence[sequence.length - 1]
 for (var i = 0;   i < sequence.length - 1;  i++) {
 if (sequence[i] > root) {
 break;
 }
 }
 for (let j = i;   j < sequence.length - 1;  j++) {
 if (sequence[j] < root) {
 return false;
 }
 }
 var left = true;
 if (i > 0) {
 left = VerifySquenceOfBST(sequence.slice(0, i));
 }
 var right = true;
 if (i < sequence.length - 1) {
 right = VerifySquenceOfBST(sequence.slice(i, sequence.length - 1));
 }
 return left && right;
 }
 }

4. The path of the binary tree neutralization for a certain value

Enter the following node and an integer of a binary tree, and print out all paths where the sum of node values in the binary tree is the input integer. A path is defined as a path from the root node of the tree down to the node through which the leaf node passes. (Note: In the list of return values, the array with large array length is at the front)

Train of thought

1. Use Preorder Traversal

2. Use an auxiliary stack to store data in the current path

3. Record the sum of a current path

4. After traversing to the current node, the current value is put into the path stack, and the current value is added

5. Recursive left child right child node

6. After traversing a node, return to the previous node, remove the current value from the path stack, and subtract the current value

Code

function FindPath(root, expectNumber) {
 var result = [];
 if (!  root) {
 return result;
 }
 findPath(root, expectNumber, [], 0, result);
 return result;
 }
 
 function findPath(node, expectNumber, vector, sum, result) {
 vector.push(node.val);
 sum += node.val;
 var isLeaf = !  node.left && !  node.right;
 if (isLeaf && sum === expectNumber) {
 result.push(vector.slice(0));
 }
 if (node.left) {
 findPath(node.left, expectNumber, vector, sum, result);
 }
 if (node.right) {
 findPath(node.right, expectNumber, vector, sum, result);
 }
 vector.pop();
 }