Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money

Hello everyone, I am quick-frozen fish 🐟, a front end of water system 💦, like colorful whistle 💐, continuous sand sculpture 🌲, I am a good brother of the next door Cold grass Whale, I just started to write an article. If you like my article, you can follow ➕ to like it, inject energy into me, and grow with me

Preface 🌧 ️

Algorithms are unfamiliar and familiar to the front-end people, and often we don’t value them as much as the back-end engineers do. But in fact, algorithms have an unshakable position for every programmer.

Because the development process is to convert the actual problem into the computer can recognize the instructions, that is, “data structure” said, “design the data structure, in the application of algorithms on the line”.

The quality of writing instructions will directly affect the performance of the program, and instructions are composed of data structure and algorithm, so the design of data structure and algorithm basically determines the quality of the final program.

In addition, when reading the source code, the lack of understanding of algorithms and data structures makes it difficult to understand why the author wrote the way he did.

In today’s environment, algorithms have become an indispensable skill for front-end engineers. If we want to move beyond being application engineers writing business code, we need to understand algorithms and data structures.

Of course, learning is also focused, as the front end we do not need to fully grasp the algorithm like back-end development, some of the more partial, not practical type and solution method, as long as a little understanding.

The title 🦀

Middle order traversal of binary trees

Difficulty is simple

Given the root node of a binary tree, return its middle-order traversal.

Example 1:

Input: root = [1,null,2,3]Copy the code

Example 2:

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

Example 3:

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

Example 4:

Input: root = [1,2] output: [2,1]Copy the code

Example 5:

Input: root = [1, NULL,2]Copy the code

Tip:

  • The number of nodes in the tree is in the range[0, 100] 内
  • -100 <= Node.val <= 100

Advanced: The recursive algorithm is simple, can you do it with an iterative algorithm?

🌵

  • Middle order traversal binary tree
  • Remember the formula left root right

How to solve the problem 🐂

  • Create a stack

  • Use a variable to point to the left node, iterate through the left subtree to push the left node onto the stack, return the value if there is none, and then point to the right node to do the same

  • Return result

Source 🔥

Non-recursive solution

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var inorderTraversal = function(root) {
   const stack=[]
    let p=root;
    const res=[]
    while(stack.length||p){
        while(p){
       stack.push(p)
        p=p.left
        }
        const n=stack.pop()
     res.push(n.val)
     p=n.right
    }
    return res

};
Copy the code

The recursive method



/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var inorderTraversal = function(root) {
/ / the recursive version
        const res=[]
        const rec=(root) = >{
            if(! root)return
            if(root.left)rec(root.left)
            res.push(root.val)
            if(root.right)rec(root.right)
        }
        rec(root)
        return res
};



Copy the code

Time complexity :O(n) (n is the number of nodes in the tree)

Space complexity :O(n)

Conclusion 🌞

So the middle order traversal of LeetCode94- binary tree of Yu Yu’s LeetCode algorithm is over. There is no shortcut for algorithm, only more writing, more practice and more summary. The purpose of this article is actually very simple, which is to urge myself to complete algorithm practice and summarize and output. I hope everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.

Add me on wechat: Sudongyuer, invite you into the group and learning the front together, become a better engineer ~ (group of qr code here – > front to go to bed early, qr code has expired, see the links to the boiling point in the comments, I will put the latest qr code in the comments section, of course, can also add me WeChat I pull you into the group, after all, I also interesting front-end, know I am not bad 🌟 ~)