897. Increasing Order Search Tree - Reverse Inorder Traversal + Generator

Jul 11, 2023#leetcode #tree #generator #stream #sicp #python50

AI Translation

This post is translated from Chinese into English through AI.View Original

AI-generated summary

The given code implements a function called "increasingBST" that performs an inorder traversal on a binary tree and returns a new binary tree with the same elements, but rearranged in increasing order. The code uses a generator function and the reduce function to achieve this.

In-order traversal does not necessarily require left, middle, and right.
This solution also does not require a queue to store, using a stream, everything is natural.

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        def gen(root):
            if not root:
                return
            yield from gen(root.right)
            yield root.val
            yield from gen(root.left)
        return reduce(lambda ans, i: TreeNode(i, None, ans), gen(root), None)
'''
        ans = None
        for i in gen(root):
            ans = TreeNode(i, None, ans)
        return ans
'''

Translation: