Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

preface

Data structure and algorithm belong to the internal work of the developer, no matter how the front-end technology changes, how the framework updates, how the version iteration, it is the same content. Always remember in the byte youth training camp, moon shadow teacher said a word, do not ask front-end learning algorithm. Everyone in computer science needs to know about algorithms and has the subconscious to write high-quality code.

Hierarchical traversal of binary tree II

1.1 Problem Description

Give you the root node of the binary tree, root, and return a bottom-up traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)

Example 1:

Enter: root = [3.9.20.null.null.15.7] Output: [[15.7], [9.20], [3]]
Copy the code

Example 2:

Enter: root = [1] Output: [[1]]
Copy the code

Example 3:

Input: root = [] Output: []Copy the code

1.2 Solution ideas

The problem of binary tree sequence traversal is usually solved by index record hierarchy. The difference in this problem is that the hierarchy is calculated from the bottom up, so first of all we can think of the easiest way to solve this problem is to store the results in an array from the top down. The array is then flipped through the Reverse method.

1.3 AC code

var levelOrderBottom = function(root) {
    const res = []
    const rec = (root,index) = >{
        if(! root)return
        if(! res[index]){ res[index] = [] } res[index].push(root.val) rec(root.left,index+1)
        rec(root.right,index+1)
    }
    rec(root,0)
    return res.reverse()
};
Copy the code

The second smallest node in a binary tree

2.1 Problem Description

Given a nonempty special binary tree, each node is positive and the number of children of each node can only be 2 or 0. If a node has two children, the value of the node is equal to the smaller of the two children.

More formally, root.val = min(root.left.val, root.right.val) always holds.

To give such a binary tree, you need to output the second smallest value of all nodes.

If the second smallest value does not exist, print -1.

Example 1:

Enter: root = [2.2.5.null.null.5.7] output:5Explanation: The minimum value is2The second smallest value is zero5 。
Copy the code

Example 2:

Enter: root = [2.2.2] Output: -1Explanation: The minimum value is2, but there is no second smallest valueCopy the code

2.2 Solution ideas

The simplest way to do this is to recursively store all the nodes in an RES array and record the minimum value of all the nodes.

  • And then sort the RES, from small to large
  • Any value greater than the smallest is returned
  • Otherwise -1 is returned

2.3 AC code

var findSecondMinimumValue = function(root) {
    const res = []
    let min = Infinity
    const rec = (root) = >{
        if(! root)return
        res.push(root.val)
        min = Math.min(root.val,min)
        rec(root.left)
        rec(root.right)
    }
    rec(root)
    res.sort((a,b) = >a-b)
    for(const val of res){
        if(val>min){
            return val
        }
    }
    return -1
};
Copy the code

Optimization, since we only need to find the smallest and the second smallest we can dispense with the process of storing values in the RES array. The implementation idea is as follows

  • Record the smallest value of all nodes
  • Because of the particularity of the problem, the value of the root node of the binary tree must be greater than or equal to the value of the left two nodes, so we only need to record the value greater than the minimum once to exit the recursion
var findSecondMinimumValue = function(root) {
    let ans = -1 
    letrootVal = root? .val// The root node is the minimum
    const rec = (root) = >{
        if(! root)return 
        if(ans! = -1&&root.val>ans){ // Find a value greater than the current second smallest value
            return
        }
        if(root.val>rootVal){ 
            ans = root.val // ans records the second smallest value so far.
        }
        rec(root.left)
        rec(root.right)
    }
    rec(root)
    return ans
};
Copy the code

conclusion

Well, this toe offer with two stacks to achieve queue to end here, I am Shao Xiaobai, a junior in the front-end field, welcome to 👍 comments.