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.

Through this kind of article with you musa binary tree symmetry problem, nonsense not to say, directly begin! 🙋

The KTH smallest element in a binary search tree

1.1 Problem Description

Given the root node of a binary search tree, root, and an integer k, design an algorithm to find the KTH smallest element (counting from 1).

Example 1:

Enter: root = [3.1.4.null.2], k = 1Output:1
Copy the code

Example 2:

Enter: root = [5.3.6.2.4.null.null.1], k = 3Output:3
Copy the code

1.2 Solution ideas

So let’s just review some of the features of binary search trees.

  • The left of the root node is smaller than the root node
  • The right node of the root is larger than the root node

Then we can quickly come up with a solution: we can store all the results in a result set by middle order traversal, and the result set must be ordered from smallest to largest, so we only need to print the KTH element.

1.3 AC code

var kthSmallest = function(root, k) {
    const res =  []
    const dfs = (root) = >{
        if(! root)return
        dfs(root.left)
        res.push(root.val) // Pay attention to the order traversal
        dfs(root.right)
    }
    dfs(root)
    return res[k-1] // count k from 1
};
Copy the code

Further optimization, then when the length of the res result set has reached k can we stop recursing.

var kthSmallest = function(root, k) {
    const res =  []
    const dfs = (root) = >{
        if(! root)return
        if(res.length>=k) return
        dfs(root.left)
        res.push(root.val)
        dfs(root.right)
    }
    dfs(root)
    return res[k-1]};Copy the code

Can we continue to optimize? The space complexity of the above solution is O(N). Since it is the KTH element in the result set that needs to be printed, why don’t we directly use a count to count? If the number of valid node recursions reaches K, we can directly return the result.

var kthSmallest = function(root, k) {
    let count = 0
    let res = 0
    const dfs = (root) = >{
        if(root&&count<=k){
           dfs(root.left)
           if(++count==k){
               res = root.val
           }
           dfs(root.right)
        }
    }
    dfs(root)
    return res
};
Copy the code

Sequence traversal of binary tree

2.1 Problem Description

Give you the root node of the binary tree, root, and return the sequential traversal of its node value. (That is, layer by layer, all nodes are accessed from left to right).

Example 1:

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

Example 2:

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

Example 3:

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

2.2 Solution ideas

The hierarchy of the tree is pretty consistent, whether it’s zigzag or if you keep it all the way from left to right, you just use index.

2.3 AC code

var levelOrder = 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
};
Copy the code

The right view of the binary tree

3.1 Title Description

Given the root node of a binary tree, root, imagine yourself standing on the right side of it and returning the values of the nodes visible from the right side, in order from top to bottom.

Example 1:

Input:1.2.3.null.5.null.4] output: [1.3.4]
Copy the code

Example 2:

Input:1.null.3] output: [1.3]
Copy the code

Example 3:

Input: [] Output: []Copy the code

3.2 Problem solving Ideas

This is a very similar problem to the last one, but it’s just a sort of order traversal problem, and this time the order level is going from right to left. And each level is evaluated only once, so it’s easy to use an array to see if each level already has a value. If it does, you don’t need to store it.

3.3 AC code

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

The maximum depth of a binary tree

4.1 Description

Given a binary tree, find its maximum depth.

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

Example:

Given a binary tree [3.9.20.null.null.15.7].3
   / \
  9  20
    /  \
   15   7Returns its maximum depth3 。

Copy the code

4.2 Solution ideas

If both of the above problems are solved, the problem is very simple, just record the maximum number of levels.

4.3 AC code

var maxDepth = function(root) {
    let max = 0
    const rec = (root,index) = >{
        if(! root)return
        max = index > max ? index : max  // Execute faster than math.max ()
        rec(root.left,index+1)
        rec(root.right,index+1)
    }
    rec(root,1)
    return max
}
Copy the code

subsequent

# [Algorithm path] 😉 Understand symmetry recursion (1)

Well, this article [algorithm path] 😉 fully understand the symmetry recursion (2) here is the end, I am Shao Xiaobai, a junior in the front-end field, welcome 👍 comments.