preface

Recently in brush force buckle binary tree related problems, found that many problems need to be solved by recursion, or many problems solved by recursion will be relatively simple. But they can not be very skilled in the use of recursive algorithm, for the recursive process of circular call recursive function this idea is often easy to fall in jump out.

Later, I read the idea of an algorithm guru: as for the implementation logic of recursion, I don’t need to fall into the recursive loop to think about what the recursion will look like after it is expanded. I just need to determine what the recursion will achieve and in which step.

To sum up:

1. First give this function a clear meaning (i.e. what is the purpose of writing this recursive function) 2. Write the boundary conditions. 3. Finally implement the recursive process (regardless of how the recursive process is executed).

So we don’t have to think about how the recursion works, we just need to know is my recursive program right, does it give me what I want

In the next section, I’ll implement this rule in code with some of the binary-tree issues I’ve been brushing up on

Brush the topic

This section will start to brush problems, I will mainly brush on the basis of the binomial tree related problems combined with recursive algorithm to summarize. I will be in accordance with the recursive rule to every question, there is wrong or have a better idea, welcome comments pointed out ~ (‘ thinking ‘part sometimes I will only write simple ideas, detailed steps will write in comments every line of code, please cooperate with code to eat ^ – ^ if you have not understand place, also welcome to leave a message in the comments section)

1. Binary tree foreorder traversal: force buckle 144 questions.

Simple recursion

The pre-order, middle-order and post-order traversal of binary trees is actually the position of root nodes (left-right root, left-right root and left-right root) when traversing binary trees, which will not be described in this paper.

Without further ado, get right to the code

/** * 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[]} */ let recursive = (root, If (root === null) return arr.push(root.val) // So place the root node in the array recursive(root.left, arr) // then place the left node in the array recursive(root.right, Return} var preorderTraversal = function(root) {let res_arr = [] // Declare an array to store the traversal result res_arr) return res_arr };Copy the code

2.N fork tree foreorder traversal: Force button 589

Define an array to store the result of traversal. Insert val of the root node into the recursive function first, then val of the child nodes

In the code

/** * // Definition for a Node. * function Node(val, children) { * this.val = val; * this.children = children; *}; */ /** * @param {Node} root * @return {number[]} */ let recursive = function(root, arr) { Root) return // boundary condition arr.push(root.val) // for (let I = 0; i < root.children.length; i++) { recursive(root.children[i], Var preorder = function(root) {let res_arr = [] recursive(root, res_arr) return res_arr};Copy the code

3. Flipping binary trees: Force button 226.

Swap the left and right subtrees of a binary tree. Then the idea is clear – traverse the binary tree and swap the left and right nodes

/** * 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 : } */ /** * @param {TreeNode} root * @return {TreeNode} */ var invertTree = function(root) {// if (! root) return null; // Boundary conditions // left and right subtrees swap positions, [root.left, root.right] = [root.right, InvertTree (root.left) invertTree(root.left) return root};Copy the code

4. Print binary trees from top to bottom: Force button sword refers to Offer32-II.

Define a k to record the number of levels of the binary tree traversed. Define a two-dimensional array to store the traversal results

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; / / * * * *} * @ param {TreeNode} root * @ return {number [] []} * / / / k which is used to mark a layer, Let recursive = (root, arr, k) => {// Traverses the binary tree from the top down if (! Root) return if (arr.length == k) arr.push([]) Arr [k]. Push (root.val) // Add val of this node to the corresponding layer of arR to traverse the left subtree. Root. Right, arr, k + 1 Var levelOrder = function(root) {let res_arr = [] recursive(root, res_arr, 0) // Pass in the initial value return res_arr};Copy the code

5. Sequence traversal of binary tree II: Force Button 107

Same as the previous problem, except that the order is traversed from the bottom up. You can just flip the results based on the previous question, without making detailed comments

let recursive = (root, k, arr) => { if (! root) return if (arr.length == k) arr.push([]) arr[k].push(root.val) recursive(root.left, k + 1, arr) recursive(root.right, k + 1, arr) return } var levelOrderBottom = function(root) { let res_arr = [] recursive(root, 0, Res_arr) return res_arr.reverse();Copy the code

6. Serrated sequence traversal of binary trees: Force button 103

Do a sequence traversal at the even-numbered levels

let recursive = (root, k, arr) => { if (! root) return; if (k === arr.length) arr.push([]) arr[k].push(root.val) recursive(root.left, k + 1, arr) recursive(root.right, k + 1, Arr)} var zigzagLevelOrder = function(root) {let res_arr = [] root (0, res_arr) Res_arr.map ((item, index) => { if((index + 1) % 2 === 0 && item.length > 1) { item = item.reverse() } }) return res_arr };Copy the code

conclusion

This paper first analyzes and explains some simple topics of binary tree correlation algorithm, mainly to deepen the understanding of recursion, and make clear the use of recursion

Recursion is an implementation of the algorithm, all involved in the loop can be used recursion

In the next article, we will continue to solve the problems related to binary trees by recursion, which will be slightly more difficult than the problems in this article. If you are interested, please give a thumbs up and continue to follow.