Record 6 algorithm problems

Binary tree forward traversal

Leetcode-cn.com/problems/bi…

It’s a simple recursion, root left and right

    function preorderTraversal(root, result = []) {
        if(! root)return result
        result.push(root.val)
        preorderTraversal(root.left, result)
        preorderTraversal(root.right, result)
        return result
    }
Copy the code

N forward traversal of a fork tree

Leetcode-cn.com/problems/n-…

There are two ways, one is recursion, the other is iteration.

The recursion is simple, just like the binary tree traversal, except that the binary tree can pass root. Left and root. Right directly. However, the number of children nodes in the n-tree is uncertain, and children need to be looped.

    function preorder(root, result = []) {
        if(! root)return result
        result.push(root.val)
        // Iterate through the collection
        if (root.children) {
          root.children.forEach(child= > preorder(child, result))
        }
        return result
    }
Copy the code

The difference between iteration and binary tree is also the uncertainty of child nodes. Recursion uses function calls to the stack, hiding the use of the stack, and iteration can also be done with a stack. Push the node into the array and pop it out, keeping the top of the stack at one of the nodes being traversed. You can push the node backwards, pushing the last node of the children first. So at the top of the stack is children, the leftmost node.

    function preorder(root) {
        if(! root)return []
        const stack = [root]
        const result = []
        while (stack.length) {
          let node = stack.pop()
          result.push(node.val)
          if ((node = node.children)) {
              // Push backwards
            for (let i = node.length - 1; i >= 0; i--) {
              stack.push(node[i])
            }
          }
        }
        return result
    }
Copy the code

Flip the binary tree

226. Flipping binary Trees – LeetCode (leetcode-cn.com)

Just go through each node and flip left and right

    function invertTree(root) {
        if(! root)return root
        const temp = root.left
        root.left = root.right
        root.right = temp
        invertTree(root.left)
        invertTree(root.right)
        return root
    }
Copy the code

Print binary tree II from top to bottom

Leetcode-cn.com/problems/co…

The requirement is to print a binary tree layer by layer, so it must be sequential traversal. But each node traversed pushes their left right into the same array. It’s important to know where each layer is bounded.

    function levelOrder(root) {
        if(! root)return []
        const result = []
        let stack = [root]
        while (stack.length) {
          const temp = []
          // Focus on how to make each layer separate. And the neat thing about this is,
          // Each time while is a layer, count the stack,
          // Separate each layer
          for (let i = stack.length; i > 0; i--) {
            const node = stack.shift()
            temp.push(node.val)
            if (node.left) {
              stack.push(node.left)
            }

            if (node.right) {
              stack.push(node.right)
            }
          }
          result.push(temp)
        }
        return result
    }
Copy the code

Sequence traversal of binary trees II

Leetcode-cn.com/problems/bi…

This problem requires that you log from the bottom layer up to the top of the array by traversing the hierarchy normally and pushing the results of each layer to the beginning of the array.

Before we do that, let’s talk about sequence traversal. Sequence traversal is breadth-first and recursion is depth-first. It means that breadth starts at the top node, and then scans the bottom node.

The usual way to do this is to push the node into the array and then take the value from the beginning of the array each time, like a queue. Because every time you push the left and right of the node. So at the end of a certain layer, it’s the beginning of the array. The next one is the left of the first node in this layer. Something like this

[b, c], shift(), shift(), shift(), shift(), shift(), shift(), shift(), shift(), shift(), shift(), shift(), shift(), shift() Now array is [c. D, e] the third time [C, d, e], shift(), get C, push c.ft, c. light into array. Now the array is [d, e, f] and then it repeats until the array length is zero. At this point all nodes are readCopy the code

As you can see, by the third time, it is already a layer 2 node.

And then how do you distinguish the boundaries of each layer. I’m going to use a temporary array. Push left right into a temporary array. When the queue array is 0, it indicates that nodes of the next layer have been collected. Just assign the temporary array to the queue array.

    function levelOrderBottom(root) {
        if(! root)return []
        let stack = [root]
        const result = []

        while (stack.length) {
          const temp = []
          // Use the current length as a marker for the boundary.
          for (let i = stack.length; i > 0; i--) {
            const node = stack.shift()
            temp.push(node.val)
            node.left && stack.push(node.left)
            node.right && stack.push(node.right)
          }
          // Insert at the beginning, and the result is from the bottom layer to the first layer
          result.unshift(temp)
        }
        return result
    }
Copy the code

Serrated sequence traversal of binary trees

Leetcode-cn.com/problems/bi…

It is required to be like a snake, with each layer facing in opposite directions. In fact, the method of sequential traversal does not change, it is still a layer by layer into the array, but can be used in the output of the array.

    function zigzagLevelOrder(root) {
        if(! root)return []
        const stack = [root]
        const result = []
        // There is a renovation here
        let a = 'push'

        while (stack.length) {
          const temp = []
          for (let i = stack.length; i > 0; i--) {
            const node = stack.shift()
            // Change direction by toggling push and unshift
            temp[a](node.val)
            node.left && stack.push(node.left)
            node.right && stack.push(node.right)
          }
          // Change it after each layer
          a = a === 'push' ? 'unshift' : 'push'
          result.push(temp)
        }
        return result
    }
Copy the code

The end of the