The title

link

parsing

A way to traverse a tree. DFS (order traversal first, order traversal middle, order traversal after); BFS.

There are two common strategies for traversing a tree:

  • Depth-first traversal (DFS)

    This approach uses a depth-first strategy to traverse from the root node to a leaf node, and then back to the root node to traverse another branch. DFS can be further subdivided into preorder traversal, inorder traversal and postorder traversal according to the access order of the root node, left child node and right child node.

  • Breadth-first traversal (BFS)

    The nodes are traversed layer by layer from top to bottom in order of height. The upper node is traversed and the lower node is traversed.

In the following figure, the corresponding subtrees are traversed in different ways, and the traversal sequence is 1-2-3-4-5. The characteristics of different traversal methods are compared according to different subtree structures.

! [img] (imgconvert. Csdnimg. Cn/aHR0cHM6Ly9… width=500 height=250)

What is the result of converting an ordered array to a binary search treeIs not the only ？

As we all know, the middle order traversal of binary search tree is an ascending sequence.

With an ordered array as input, the problem can be thought of as creating a binary search tree from a middle-order traversal sequence.

There’s only one answer to that question. For example, whether a sequence can be traversed according to the middle order and whether there is a one-to-one correspondence between binary search trees, the answer is no.

Here are some facts about BST.

  • Middle order traversal cannot uniquely identify a binary search tree.
  • Pre-order and post-order traversal do not uniquely determine a binary search tree.
  • The relation between pre-order/post-order traversal and middle-order traversal:

    inorder = sorted(postorder) = sorted(preorder).
  • Middle-order + post-order and middle-order + preorder can uniquely determine a binary tree.

Therefore, “ordered array -> BST” has multiple answers.

Therefore, add an attachment condition:The height of the tree should be balancedFor example, the height difference between two subtrees of each node is less than or equal to 1.

Is the answer unique in this case? Still not.

Highly balanced means that the middle number must be selected as the root node every time. This is useful for an odd number of arrays, but there is no predefined selection scheme for an even number of arrays.

For an even number of arrays, either the element to the left of the middle position is selected as the root node, or the element to the right of the middle position is selected as the root node. Different selection schemes create different balanced binary search trees. Method one always selects the element to the left of the center as the root node, and method two always selects the element to the right of the center as the root node. Methods 1 and 2 generate different binary search trees, and both answers are correct.

Method 1: middle-order traversal: Always select the element to the left of the middle position as the root node

algorithm

  • The helper(left, right) method creates a BST using elements indexed from left to right in the array nums:

    • ifleft > right, there is no element in the subtree, return null.
    • Find the middle element:p = (left + right) // 2.
    • Create the root node:root = TreeNode(nums[p]).
    • Recursively create the left subtreeroot.left = helper(left, p - 1)And right subtreeroot.right = helper(p + 1, right).

  • Return Helper (0, len(nums) -1).

Code:

class Solution {
  int[] nums;

  public TreeNode helper(int left, int right) {
    if (left > right) return null;

    // always choose left middle node as a root
    int p = (left + right) / 2;

    // inorder traversal: left -> node -> right
    TreeNode root = new TreeNode(nums[p]);
    root.left = helper(left, p - 1);
    root.right = helper(p + 1, right);
    return root;
  }

  public TreeNode sortedArrayToBST(int[] nums) {
    this.nums = nums;
    return helper(0, nums.length - 1); }}Copy the code

Complexity analysis

  • Time complexity: O(N), each element is accessed only once.
  • Space complexity: O(N), binary search tree space O(N), recursive stack depth O(logN).

Method 2: middle-order traversal: always select the element to the right of the middle position as the root node

algorithm

  • The helper(left, right) method creates a BST using elements indexed from left to right in the array nums:

    • If left > right, there is no element in the subtree, return null.

    • Find the element to the right of the middle position:

      • p = (left + right) // 2.
      • ifleft + rightIs even, thenp + 1.

    • Create a root node: root = TreeNode(nums[p]).

    • Recursively create the left subtree root.left = helper(left, p-1) and the right subtree root.right = helper(p + 1, right).

  • Return Helper (0, len(nums) -1).

class Solution {
  int[] nums;

  public TreeNode helper(int left, int right) {
    if (left > right) return null;

    // always choose right middle node as a root
    int p = (left + right) / 2;
    if ((left + right) % 2= =1) ++p;

    // inorder traversal: left -> node -> right
    TreeNode root = new TreeNode(nums[p]);
    root.left = helper(left, p - 1);
    root.right = helper(p + 1, right);
    return root;
  }

  public TreeNode sortedArrayToBST(int[] nums) {
    this.nums = nums;
    return helper(0, nums.length - 1); }}Copy the code

Complexity analysis

  • Time complexity: O(N), each element is accessed only once.
  • Space complexity: O(N), binary search tree space O(N), recursive stack depth O(logN).

Method 3: middle order traversal: select any middle element as the root node

The root node is randomly selected to the left or right of the middle position each time without predefined selection. The result of each run is different, but correct.

algorithm

  • The helper(left, right) method creates a BST using elements indexed from left to right in the array nums:

    • If left > right, there is no element in the subtree, return null.

    • Find the element to the right of the middle position:

      • p = (left + right) // 2.
      • ifleft + rightIt’s even. It’s randomp + 0orp + 1.

    • Create a root node: root = TreeNode(nums[p]).

    • Recursively create the left subtree root.left = helper(left, p-1) and the right subtree root.right = helper(p + 1, right).

  • Return Helper (0, len(nums) -1).

class Solution {
    int[] nums;
    Random rand = new Random();
    
    public TreeNode helper(int left, int right) {
        if (left > right) return null;
        
        // choose random middle node as a root
        int p = (left + right) / 2; 
        if ((left + right) % 2= =1) p += rand.nextInt(2);

        // inorder traversal: left -> node -> right
        TreeNode root = new TreeNode(nums[p]);
        root.left = helper(left, p - 1);
        root.right = helper(p + 1, right);
        return root;
    }
    
    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return helper(0, nums.length - 1); }}Copy the code

Complexity analysis

  • Time complexity: O(N), each element is accessed only once.
  • Space complexity: O(N), binary search tree space O(N), recursive stack depth O(logN).