preface

Record the leetcode problem for the day

Topic describes

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

Train of thought

  1. First, check whether the node currently traversed is null, and return null if null
  2. Check whether the current node has left and right subtrees
  3. Returns val of the current node
  4. Right subtree does not exist, recursive traversal returns the left subtree, enclosing parentheses
  5. Traverse the left subtree, enclosing parentheses. Iterate over the right subtree, enclosing parentheses

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 {string}* /
 var tree2str = function(root) {
     if(root == null) return ' '
     if(! root.left && ! root.right) {return ' ' + root.val
 
     }
     if(root.right == null) {
        return root.val + '(' + tree2str(root.left) + ') '
     }
     return root.val + '(' + tree2str(root.left) + ') (' + tree2str(root.right) + ")"
 }
Copy the code

The last

Make a little progress every day