This is the 10th day of my participation in the More text Challenge. For more details, see more text Challenge

Trees with similar leaves (Question Number 872)

The title

Consider all the leaves in a binary tree whose values are arranged from left to right to form a sequence of leaf values.

For example, as shown in the figure above, give a tree with a sequence of leaf values (6, 7, 4, 9, 8).

If two binary trees have the same sequence of leaf values, then we consider them leaf similar.

Return true if the tree with root1 and root2 roots is leaf similar; Otherwise return false.

Example 1:

Input: root1 = [3,5,1,6,2,9,8, null, null, 7, 4], root2 = [3,5,1,6,7,4,2, null, null, null, null, null, null, 9, 8] output: trueCopy the code

Example 2:

Input: root1 = [1], root2 = [1] Output: trueCopy the code

Example 3:

Input: root1 = [1], root2 = [2] Output: falseCopy the code

Example 4:

Input: root1 = [1,2], root2 = [2,2] output: trueCopy the code

Example 5:

Input: root1 = [1,2,3], root2 = [1,3,2] output: falseCopy the code

Tip:

  • Given two trees, there might be1 到 200A node.
  • The values of the given two trees are between0 到 200In between.

link

Leetcode-cn.com/problems/le…

explain

This one. This one is a punch.

This is actually a very simple problem, just go through two trees, it’s not technically difficult.

The important thing is the implementation, because you can choose what you want to do, in order, before order, after order, whatever you want.

Your own answer (iteration)

var leafSimilar = function(root1, root2) { function checkLeaf(node, leaves) { if (! node.left && ! node.right) leaves.push(node.val) } function getLeaves(root) { var stack = [root] leaves = [] while (stack.length) { root = stack.pop() checkLeaf(root, leaves) root.right && stack.push(root.right) root.left && stack.push(root.left) } return leaves.toString() } return getLeaves(root1) === getLeaves(root2) };Copy the code

Let’s do a getLeaves function to get the leaves of the tree. The internal implementation of the getLeaves function is a simple, preorder iterating walk that ends with toString() returning an array.

Your own answer (recursion)

var leafSimilar = function(root1, root2) { function getLeaves(root) { if (! root) return [] if (! root.left && ! root.right) return [root.val] return getLeaves(root.left).concat(getLeaves(root.right)) } return getLeaves(root1).toString() === getLeaves(root2).toString() };Copy the code

Recursion is simpler at the code level, but with one caveat.

In the iterated answer, the final return value is left.tostring (), but in the recursion, only the array is returned, and you need to operate on the outer layer.

According to? If toString() is returned, it will be toString() halfway through the recursion, and the final answer will have numbers stuck together, just like the leaves in the tree.

It’s not hard after that.

A better way

There is no




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