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

Topic describes

This is 606 on LeetCode. Create a string from a binary tree.

Tag: binary tree, DFS, recursion, iteration, stack

You need to convert a binary tree to a string of parentheses and integers using a sequential traversal.

Empty nodes are represented by a pair of empty parentheses “()”. And you need to omit any empty parenthesis pairs that do not affect the one-to-one mapping between the string and the original binary tree.

Example 1:

Input: binary tree: 1/2 3/4 \ [1, 2, 3, 4] output: "1 (2) (4) and (3)" explanation: that will be "1 (2 (4) the ()) () (3)", after you omit all unnecessary parentheses to empty, it will be "1 (2) (4) and (3)".Copy the code

Example 2:

Input: binary tree: [1,2,3, NULL,4] 1 / \ 2 3\4 Output: "1(2()(4))(3)" Explanation: Similar to the first example, except that we cannot omit the first pair of parentheses to break the one-to-one mapping between input and output.Copy the code

recursive

The rule for generating strings is to add a pair of () to the left and right of each subtree (except for the root node) while “pre-traversing” the output node values, while ignoring unnecessary ().

The so-called unnecessary means that when the root of node XXX is “left subtree” and “no right subtree”, the () of the right subtree can be ignored, or the () of both can be ignored when there is “neither left nor right subtree”.

Or conversely, if for every node to add () is not empty, then when “right subtree” “there is no left subtree” at the same time, the left subtree () can not be ignored, need extra, to ensure that the generated string to “have left subtree” are “no right subtree” at the same time, without ambiguity.

Code:

class Solution {
    StringBuilder sb = new StringBuilder();
    public String tree2str(TreeNode root) {
        dfs(root);
        return sb.substring(1, sb.length() - 1);
    }
    void dfs(TreeNode root) {
        sb.append("(");
        sb.append(root.val);
        if(root.left ! =null) dfs(root.left);
        else if(root.right ! =null) sb.append("()");
        if(root.right ! =null) dfs(root.right);
        sb.append(")"); }}Copy the code
  • Time complexity: Let the number of points be NNN and the number of edges be MMM. The overall complexity is O(n+m)O(n +m)O(n +m)
  • Space complexity: O(n)O(n)O(n)

Iteration (non-recursive)

It is also possible to do this “iteratively (non-recursively)”, using stacks to simulate the recursive process described above.

Because when XXX is the root node of a node, it needs to be added (, and added before the end) when the current subtree is traversed in sequence before the start, a node needs to enter and exit the queue twice.

To distinguish between the first exit (traversal before the start) and the second exit (traversal before the end), a set is used for recording, and the rest of the logic is similar to “recursive”.

Code:

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Set<TreeNode> vis = new HashSet<>();
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while(! d.isEmpty()) { TreeNode t = d.pollLast();if (vis.contains(t)) {
                sb.append(")");
            } else {
                d.addLast(t);
                sb.append("(");
                sb.append(t.val);
                if(t.right ! =null) d.addLast(t.right);
                if(t.left ! =null) d.addLast(t.left);
                else if(t.right ! =null) sb.append("()"); vis.add(t); }}return sb.substring(1, sb.length() - 1); }}Copy the code
  • Time complexity: Let the number of points be NNN and the number of edges be MMM. The overall complexity is O(n+m)O(n +m)O(n +m)
  • Space complexity: O(n)O(n)O(n)

Iteration (general non-recursive)

The above “iterative (non-recursive)” solution, we still need to do a simple analysis of the topic.

By using the general technique of “recursive” to “non-recursive”, we can directly rewrite the “recursive” solution, and the use of loC in the general non-recursive process can help us to avoid the set structure used to distinguish whether the team is out for the first time.

It’s important to note that since modern compilers have done so much to optimize recursion, this technique is no longer necessary.

Code:

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Deque<Object[]> d = new ArrayDeque<>();
        d.addLast(new Object[]{0, root});
        while(! d.isEmpty()) { Object[] poll = d.pollLast();int loc = (Integer)poll[0]; TreeNode t = (TreeNode)poll[1];
            if (loc == 0) {
                sb.append("(");
                sb.append(t.val);
                d.addLast(new Object[]{1, t});
            } else if (loc == 1) {
                d.addLast(new Object[]{2, t});
                if(t.right ! =null) d.addLast(new Object[]{0, t.right});
                if(t.left ! =null) d.addLast(new Object[]{0, t.left});
                else if(t.right ! =null) sb.append("()");
            } else if (loc == 2) {
                sb.append(")"); }}return sb.substring(1, sb.length() - 1); }}Copy the code
  • Time complexity: Let the number of points be NNN and the number of edges be MMM. The overall complexity is O(n+m)O(n +m)O(n +m)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.606 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.