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

68

606. Create strings based on binary trees

  • Leetcode: leetcode-cn.com/problems/co…
  • Difficulty: Easy
  • Methods: DFS

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.

The sample

  • 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

Thought analysis

The first reading comprehension

  • Preorder traversal – > middle left and right
  • For each root node, the elements to the left and right are enclosed in parentheses.
  • However, when I ran the test sample, I found that the problem was not to put the left and right nodes in one parenthesis, but to put each node in one parenthesis. Parentheses enclose parentheses.
  • So the correct way to do it is to print the correct answer that is not omitted, and then think about how to omit it. Right

The final question is understood

  • Judge the circumstances: there are only four
    1. There’s a left node, there’s a right node
    2. The left node exists, but the right node does not exist
    3. There is no left node, there is a right node
    4. There is no left node, there is no right node -> needs to be omitted
  • Conclusion: There is no right node, and the left node may or may not exist
    • If the left node exists, the output operation is normal. If the right node does not exist, the output operation needs to be omitted

ACcode

/** * 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) {
  // Foreorder traversal: middle left and right
  // The left subtree prints the left parenthesis, and the right subtree prints the right parenthesis
  // Parentheses that can be removed: parentheses to the right of a number, when the right subtree is empty
  // 1. Return values and parameters: None, each node
  // 2. Terminating condition: when the node is empty
  // 3. Logic for each layer: Iterate over the current left and right nodes and add parentheses
  let ans = [];
  function dfs(node) {
    // We also need to determine whether it is the left node or the right node
    if(node == null) return;
    ans.push(node.val)
    if(node.right == null && node.left == null){
      dfs(node.left);
    }else {
      ans.push('(');
      dfs(node.left);
      ans.push(') ');
    }
    if(node.right ! =null){
      ans.push('(');
      dfs(node.right);
      ans.push(') ');
    }
  }
  dfs(root)
  return ans.join(' ')};Copy the code

conclusion

  • DFSThree steps. Make sure you think about each step.
  • It can be used based on the existing binary treedfsOr the way of iteration, before order, middle order and after order traversal
  • Foreword: middle left; Middle order: left middle right; Postsequence: middle left and right