পাইথনে প্রिअর্ডার ট্রভার্সাল থেকে বাইনারি সার্চ ট্রি নির্মাণ

মনে করুন আমাদের একটি বাইনারি সার্চ ট্রি তৈরি করতে হবে যা দেওয়া প্রিঅর্ডার ট্রভার্সালের সাথে মেলে। ইনপুট যদি [8,5,1,7,10,12] হয়, তবে আউটপুট হবে [8,5,10,1,7,null,12], ট্রিটি হবে:

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (স্ট্যাক ব্যবহার করে ইটারেটিভ):

• root := preorder[0] দিয়ে রুট নোড বানান।

• stack := [root]

• preorder[1:]-এর প্রতিটি এলিমেন্ট i জন্য:

  • i := TreeNode(i)

  • যদি i.val < stack[-1].val:

    • stack[-1].left = i

    • stack.append(i)

  • অন্যথায়:

    • while stack and stack[-1].val < i.val:

      • last = stack.pop()

    • last.right = i

    • stack.append(i)

• return root

উদাহরণ

class Solution(object):
    def bstFromPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: TreeNode
        """
        root = TreeNode(preorder[0])
        stack = [root]
        for i in preorder[1:]:
            i = TreeNode(i)
            if i.val < stack[-1].val:
                stack[-1].left = i
                stack.append(i)
            else:
                while stack and stack[-1].val < i.val:
                    last = stack.pop(-1)
                last.right = i
                stack.append(i)
        return root

ইনপুট

[8,5,1,7,10,12]

আউটপুট

[8,5,10,1,7,null,12]