1008-kir3i.md

1008. Construct Binary Search Tree from Preorder Traversal

Solution

• 시간복잡도: balanced BST인 경우 O(NlogN). 최악의 경우 O(N^2)

• 알고리즘

  구현, BST

• 풀이설명

  전위순회의 결과가 입력으로 주어지므로 들어오는 순서대로 BST에 넣으면 됩니다. BST의 특성에 따라 val을 보고 왼쪽 subtree에 매달지, 오른쪽 subtree에 매달지만 결정하면 됩니다.

• 소스코드

  • C++

  class Solution {
  public:
      TreeNode* bstFromPreorder(vector<int>& preorder) {
          int sz = preorder.size();
          TreeNode *root = new TreeNode(preorder[0]);
          for (int i = 1; i < sz; i++) {
              pushNode(root, new TreeNode(preorder[i]));
          }
  
          return root;
      }
  
      void pushNode(TreeNode *root, TreeNode *child) {
          if (child->val < root->val)
              if (root->left)	pushNode(root->left, child);
              else   root->left = child;
          else
              if (root->right) pushNode(root->right, child); 
              else	root->right = child;
      }
  };

  • Python

  class Solution:
      def bstFromPreorder(self, preorder):
          root = TreeNode(preorder[0])
          for n in preorder[1:]:
              self.pushNode(root, TreeNode(n))
          return root
  
      def pushNode(self, root, child):
          if child.val < root.val:
              if root.left:
                  self.pushNode(root.left, child)
              else:
                  root.left = child
          else:
              if root.right:
                  self.pushNode(root.right, child)
              else:
                  root.right = child