This is the 16th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

Hello, everyone, today is the 16th day I participated in the August more text, today brings you about the binary tree related algorithm problem is to find the binary tree of increasing order search tree, the text is as follows:

The title

Given a binary search tree, you walk through it in the middle order and rearrange it into an ascending order search tree, so that the leftmost node in the tree becomes the root node of the tree, and each node has no left child and only one right child.

Example 1

Input: root = [5,3,6,2,4, null, 8, 1, null, null, null, 7, 9] output: [1, null, 2, null, 3, null, 4, null, 5, null, 6, null, 7, null, 8, null, 9]Copy the code

Example 2

Input: root = [5,1,7] Output: [1, NULL,5,null,7]Copy the code

Their thinking

According to the problem, we are given a binary search tree, and according to the characteristics of binary search trees, if we go through it in order, we will get an ordered array, so we can save the results in a list; Then, according to the values in the list, the nodes are created, and the created nodes are built into a binary tree containing only the right node, which is a binary search tree in increasing order.

The creation process is as follows:

  1. Create a dummyNode, dummyNode, to hold the head node;
  2. Create a pointer curr to dummyNode;
  3. Iterating through the ordered array, creating nodes, and pointing the right pointer to the curr node to the newly created node;
  4. Curr points to its right subtree (equivalent to the list backwards);
  5. At the end of the loop, return the right pointer to dummyNode;

Code implementation

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    private List<Integer> arr;
    
    public TreeNode increasingBST(TreeNode root) {
        arr = new ArrayList();
        inOrder(root);
        TreeNode dummyNode = new TreeNode(-1);
        TreeNode curr = dummyNode;
        for (int val : arr) {
            curr.right = new TreeNode(val);
            curr = curr.right;
        }
        return dummyNode.right;
    }

    public void inOrder(TreeNode root) {
        if (root == null) {
            return; } inOrder(root.left); arr.add(root.val); inOrder(root.right); }}Copy the code

The last

Complexity analysis:

  • Time complexity: O(n), where n is the total number of nodes in the binary search tree.

  • Space complexity: O(n), where n is the total number of nodes in the binary search tree. A list of length n is required to hold the values of all nodes of the binary search tree.