Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

606. Create string from binary tree

606. Create string according to binary tree, simple

I. Title Description:

Friends, what do you feel when you see this problem?

This is another binary tree problem, and this time we’re going to go through this tree using a pre-order traversal, and this tree is a binary tree

Look at the title, just a part of the previous tree title to add parentheses logic, there will be no special SAO operation

Ii. Analysis of Ideas:

1. What ideas does this question examine? What’s your thinking?

So if we look at this problem, we can analyze it, what are the things that we need to think about?

  • This tree is a binary tree, and we need to use the way of pre-order traversal to deal with it. The traversal order of pre-order traversal is left and right of the root node, first traversal of the root node, then traversal of the left node, and finally traversal of the right node. I believe this XDM is familiar with

  • As we traverse the tree, parentheses are not required for the root of the entire tree, but for every node involved in the other subtrees

  • For adding parentheses, we also need to make it clear that parentheses can be ignored when the right child of the subtree is empty, because it does not affect the one-to-one mapping between the string and the original binary tree

    For example, the result of binary tree traversal: 1(2(4))(3) we know that 4 is the left subtree of 2, 2 is the left subtree of 1, and 3 is the right subtree of 1, so we do not need to write 1(2(4)())(3).

  • If the left subtree is empty and the right subtree has a value, then the empty parenthesis of the left subtree cannot be omitted. If it is omitted, it will affect the one-to-one mapping between the string and the original binary tree

    For example, the binary tree traversal result: 1(2()(4))(3), we know that 4 is the right subtree of 2. If the parentheses behind 2 are removed, it means that 4 is the left subtree of 2, which does not meet the meaning of the question

Based on the above, we can draw a schematic diagram to reason with examples:

For example, Example 1: binary tree: [1,2,3,4]

From the figure above, we can know that when traversing the root nodes of 1, 2, 4 and 3 respectively, we can add parentheses according to the rules of the above analysis. The general logic is as follows:

  • If the node has no subtree, its own value is added directly to the result set
  • If the left child of the node is empty and the right child has a value, then the empty parentheses of the left child are drawn, and the right child has a value, then the parentheses are drawn
  • If the left child of the node has a value and the right child has a value, then the parentheses of the left and right children are drawn
  • If the left child of the node has a value and the right child is empty, the parentheses of the left child are drawn and the parentheses of the right child are omitted

2. Try coding

According to the above logic and deduction, the idea is very simple, that is, according to each node traversed, to do the above logic check, according to the logic to add parentheses

The encoding is as follows:

func tree2str(root *TreeNode) string {
    switch {
    case root == nil:
        return ""
    case root.Left == nil && root.Right == nil:
        return strconv.Itoa(root.Val)
    case root.Right == nil:
        return fmt.Sprintf("%d(%s)", root.Val, tree2str(root.Left))
    default:
        return fmt.Sprintf("%d(%s)(%s)", root.Val, tree2str(root.Left), tree2str(root.Right))
    }
}
Copy the code

It can be seen that our code ** is to translate our thoughts above **, so when we do the problem, we need to think clearly first, figure out the whole process and ideas, so when coding, it is a translation process, the focus is thought

Iv. Summary:

The time complexity and the space complexity are both O(n), and the main reason is that we have to think about each of these cases, and we can do this very quickly

Create a string from a binary tree

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~