1008. Construct Binary Search Tree from Preorder Traversal.md

1008. Construct Binary Search Tree from Preorder Traversal

---

Difficulty : Medium

Related Topics : Tree

---

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Constraints:

• 1 <= preorder.length <= 100
• 1 <= preorder[i] <= 10^8
• The values of preorder are distinct.

---

Solution

• mine
  • Java

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.8 MB, less than 24.34% of Java online submissions

      //O(N^2)time
      //O(N)space
      public TreeNode bstFromPreorder(int[] preorder) {
          TreeNode res = new TreeNode(preorder[0]);
          if(preorder.length == 1){
              return res;
          }
          for(int i = 1; i < preorder.length; i++){
              setNode(res,preorder[i]);
          }
          return res;
      }
      
      public void setNode(TreeNode node, int val){
          if(node.val < val){
              if(node.right == null){
                  node.right = new TreeNode(val);
              }else{
                setNode(node.right,val);
              }
          }else {
               if(node.left == null){
                  node.left = new TreeNode(val);
              }else{
                setNode(node.left,val);
              }
          }
      }
      

    • Iteration Runtime: 1 ms, faster than 38.48%, Memory Usage: 39.1 MB, less than 5.25% of Java online submissions

      // O(N)time
      // O(N)space
      public TreeNode bstFromPreorder(int[] preorder) {
          TreeNode root = new TreeNode(preorder[0]);
          LinkedList<TreeNode> list = new LinkedList<>();
          list.add(root);
          int index = 1;
          while(index < preorder.length){
              TreeNode n = list.getLast();
              TreeNode t = new TreeNode(preorder[index]);
              index++;
              if(t.val < n.val){
                  n.left = t;
              }else{
                  while(!list.isEmpty() && list.getLast().val < t.val){
                      n = list.removeLast();
                  }
                  n.right = t;
              }
              list.add(t);
          }
          return root;
      }
      

---