পাইথনে বাইনারি ট্রি জিগজ্যাগ লেভেল অর্ডার ট্রভার্সাল

মনে করুন আমাদের একটি বাইনারি ট্রি আছে, আমাদের এর জিগজ্যাগ লেভেল অর্ডার ট্রভার্সাল বের করতে হবে। প্রথম রো লেফট-টু-রাইট, দ্বিতীয় রো রাইট-টু-লেফট, তারপর আবার লেফট-টু-রাইট, এভাবে চলবে।

ট্রি যদি নিচের মতো হয়:

তবে ট্রভার্সাল সিকোয়েন্স হবে [[3],[20,9],[15,7]]।

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

• যদি ট্রি খালি হয়, তবে খালি লিস্ট রিটার্ন করুন।

• queue := [root], res := [], res2 := [], flag := True

• while queue not empty:

  • res.append([i for i in queue]) (নোড লিস্ট)

  • res2.append([i.data for i in queue if i.data != 0]) (ভ্যালু লিস্ট)

  • queue = [] (নেক্সট লেভেলের জন্য খালি করুন)

  • যদি flag true হয়:

    • i = len(res[-1]) - 1

    • while i >= 0:

      • যদি res[-1][i].right থাকে, তবে কিউতে অ্যাপেন্ড করুন।

      • যদি res[-1][i].left থাকে, তবে কিউতে অ্যাপেন্ড করুন।

      • i--

  • অন্যথায় (flag false):

    • i = len(res[-1]) - 1

    • while i >= 0:

      • যদি res[-1][i].left থাকে, তবে কিউতে অ্যাপেন্ড করুন।

      • যদি res[-1][i].right থাকে, তবে কিউতে অ্যাপেন্ড করুন।

      • i--

  • flag = not flag

• return res2

উদাহরণ

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def zigzagLevelOrder(self, root):
        if not root:
            return []
        queue = [root]
        res = []
        res2 = []
        flag = True
        while len(queue) != 0:
            res.append([i for i in queue])
            res2.append([i.data for i in queue if i.data != 0])
            queue = []
            if flag:
                i = len(res[-1]) - 1
                while i >= 0:
                    if res[-1][i].right:
                        queue.append(res[-1][i].right)
                    if res[-1][i].left:
                        queue.append(res[-1][i].left)
                    i -= 1
            else:
                i = len(res[-1]) - 1
                while i >= 0:
                    if res[-1][i].left:
                        queue.append(res[-1][i].left)
                    if res[-1][i].right:
                        queue.append(res[-1][i].right)
                    i -= 1
            flag = not flag
        return res2

ob = Solution()
tree = make_tree([3,9,20,None,None,15,7])
print(ob.zigzagLevelOrder(tree))

ইনপুট

[3,9,20,null,null,15,7]

আউটপুট

[[3], [20, 9], [15, 7]]