897. Increasing order search tree

Answer:

  1. Using middle order traversal, each node of the binary search tree can be obtained sequentially.

  2. Create a new tree and use leaf to represent its leaf nodes.

  3. Each time the node is traversed, the following operations are performed:

    • Connect the nodes traversed toleaf.right.
    • willleafMove to theleaf.rightKeep it pointing at the leaf node.
    • willleaf.leftSet tonullTo break the original connection of the node and avoid the ring in the new tree.
/ * * *@param {TreeNode} root
 * @return {TreeNode}* /
var increasingBST = function (root) {
  let dummy = new TreeNode() Dummy. Right points to the root of the new tree
  let leaf = dummy // Create a leaf node that points to the leaf of the new tree with an initial value of dummy

  // Build a new tree using mid-order traversal
  function traversal (node) {
    // Exit recursion when an empty node is encountered
    if(! node) {return null
    }

    // Left subtree traversal
    traversal(node.left)

    // Use a middle-order traversal to get each node in order
    // Connect the current node to the right child of the leaf node
    leaf.right = node
    // Move leaf to the right child node to connect to the next node
    leaf = leaf.right
    // Set left to null to break the node's original connection and avoid loops in the new tree
    leaf.left = null

    // Traverse the right subtree
    traversal(node.right)
  }
  traversal(root)

  Dummy. Right points to the root of the new tree
  return dummy.right
}
Copy the code