Nuggets team number online, help you Offer rimmon! Click to see details

Sequence traversal of binary trees (Question No. 102)

The title

Given a binary tree, you are asked to return the values of the nodes it traverses sequentially. (that is, access all nodes layer by layer, from left to right).

Example:

Binary tree: [3,9,20,null,null,15,7]

    3

   / \
  9  20
    /  \
   15   7
Copy the code

Return the result of its sequential traversal:

[[3], [9,20], [15,7]Copy the code

link

Leetcode-cn.com/problems/bi…

explain

This problem actually feels relatively simple, is a layer of loop with nodes, there is no logical need to pay attention to, is the code writing has some problems that need to pay attention to, look at 👇 code to know.

Your own answer

var levelOrder = function(root) { if (! root) return [] var arr1 = [root] arr2 = [] while (arr1.length > 0) { const { val, root } = arr1.reduce((total, item) => { total.val.push(item.val) item.left && total.root.push(item.left) item.right && total.root.push(item.right) return total }, { val: [], root: [] }) arr1 = root arr2.push(val) } return arr2 };Copy the code

Arr1 is used to store the node and ARR2 is used to store the final value.

It goes without saying that you prefer to handle cases where root does not exist.

Then we start iterating through ARR1, if it exists, then we loop through its contents, we do two things, first we get the value of the current node, then we get the left node and the right node, and then we put it in ARR1 and ARR2, respectively.

At the beginning, I used map. After thinking about it, I used Reduce. The code does look better, but I feel that there is no essential change.

A better way

var levelOrder = function(root) { if (! root) return [] var arr1 = [root] arr2 = [] while (arr1.length > 0) { var arrL = arr1.length arr2.push([]) for (let i = 0; i < arrL; i++) { const node = arr1.shift(); arr2[arr2.length - 1].push(node.val) node.left && arr1.push(node.left) node.right && arr1.push(node.right) } } return arr2 };Copy the code

Instead of creating two new variables to store nodes and values, I’m using the while feature. Even if I modify arR1 internally, it’s not affected until the end of the while loop, so I can safely handle arR1 and ARR2.

First, take the length of arR1 before the loop, and then a for loop. At this point, you can determine how many nodes should be taken from ARR1, but not too many, and get the nodes of the next loop.

Arr2 is much simpler. We insert an empty array into arR2 before the start of the for loop, and then we insert the value directly into the last element of arR2. We don’t need to create a new variable to store the val from the for loop.

That’s it in a nutshell, nothing else, but the details are not in place and need to be improved.

The maximum depth of a binary tree (Question number 104)

The title

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: A leaf node is a node with no child nodes.

Example: given a binary tree [3,9,20,null,null,15,7]

   3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns its maximum depth of 3.

link

Leetcode-cn.com/problems/ma…

explain

There are two main ways to solve this problem, one is Breadth First algorithm (raip-first-search), the other is Depth First algorithm (raip-first-search)

Your own answer (breadth first algorithm)

var maxDepth = function(root) { if (! root) return 0 var level = 0 nodes = [root] while (nodes.length > 0) { var nL = nodes.length for (let i = 0; i < nL; i++) { var node = nodes.shift() node.left && nodes.push(node.left) node.right && nodes.push(node.right) if (i === nL - 1) level++ } } return level };Copy the code

There’s nothing to say about that, because the last problem was very similar, you go through all the nodes horizontally, and then you accumulate the number of layers

Your own answer (depth-first algorithm)

var maxDepth = function (node, length = 0) {
  if (node) {
    var left = maxDepth(node.left, length + 1)
    right = maxDepth(node.right, length + 1)
    return Math.max(left, right) || 1 + length
  } else {
    return 0
  }
};
Copy the code

This method looks good, and is pure out of their own, there is no reference to other materials or anything. But, as always, there are some minor flaws, like in this line of work:

return Math.max(left, right) || 1 + length
Copy the code

It feels a little strange here, and it’s like this:

return Math.max(1, left, right) + length
Copy the code

But how to calculate the wrong, and then accidentally tried to write one of the above, and then it was right, and then it was very puzzling, why is it right? If math. Max is 0, return 1 + length, and the whole logic is correct.

Think about it, if it still doesn’t make sense.

Better answers (depth-first algorithm)

const maxDepth = (root) => {
  if (root == null) return 0;
  const leftMaxDepth = maxDepth(root.left);
  const rightMaxDepth = maxDepth(root.right);
  return 1 + Math.max(leftMaxDepth, rightMaxDepth);
};
Copy the code

, after all, is the first time to write depth-first algorithm looked at other people, find themselves still have room to improve, first of all, it can be the root does not exist, the condition of the follow-up is don’t need a second length parameter, you just need to every time the cumulative 1, then the recursive call, this in fact and the square that topic is a bit like, You don’t need a length at all, you don’t need it in the recursion.

So after writing code don’t worry, think carefully in writing, will be a lot clearer.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ