<p>You are given <code>n</code> <strong>BST (binary search tree) root nodes</strong> for <code>n</code> separate BSTs stored in an array <code>trees</code> (<strong>0-indexed</strong>). Each BST in <code>trees</code> has <strong>at most 3 nodes</strong>, and no two roots have the same value. In one operation, you can:</p>

<ul>
	<li>Select two <strong>distinct</strong> indices <code>i</code> and <code>j</code> such that the value stored at one of the <strong>leaves </strong>of <code>trees[i]</code> is equal to the <strong>root value</strong> of <code>trees[j]</code>.</li>
	<li>Replace the leaf node in <code>trees[i]</code> with <code>trees[j]</code>.</li>
	<li>Remove <code>trees[j]</code> from <code>trees</code>.</li>
</ul>

<p>Return<em> the <strong>root</strong> of the resulting BST if it is possible to form a valid BST after performing </em><code>n - 1</code><em> operations, or</em><em> </em><code>null</code> <i>if it is impossible to create a valid BST</i>.</p>

<p>A BST (binary search tree) is a binary tree where each node satisfies the following property:</p>

<ul>
	<li>Every node in the node&#39;s left subtree has a value&nbsp;<strong>strictly less</strong>&nbsp;than the node&#39;s value.</li>
	<li>Every node in the node&#39;s right subtree has a value&nbsp;<strong>strictly greater</strong>&nbsp;than the node&#39;s value.</li>
</ul>

<p>A leaf is a node that has no children.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/d1.png" style="width: 450px; height: 163px;" />
<pre>
<strong>Input:</strong> trees = [[2,1],[3,2,5],[5,4]]
<strong>Output:</strong> [3,2,5,1,null,4]
<strong>Explanation:</strong>
In the first operation, pick i=1 and j=0, and merge trees[0] into trees[1].
Delete trees[0], so trees = [[3,2,5,1],[5,4]].
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/24/diagram.png" style="width: 450px; height: 181px;" />
In the second operation, pick i=0 and j=1, and merge trees[1] into trees[0].
Delete trees[1], so trees = [[3,2,5,1,null,4]].
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/24/diagram-2.png" style="width: 220px; height: 165px;" />
The resulting tree, shown above, is a valid BST, so return its root.</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/d2.png" style="width: 450px; height: 171px;" />
<pre>
<strong>Input:</strong> trees = [[5,3,8],[3,2,6]]
<strong>Output:</strong> []
<strong>Explanation:</strong>
Pick i=0 and j=1 and merge trees[1] into trees[0].
Delete trees[1], so trees = [[5,3,8,2,6]].
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/24/diagram-3.png" style="width: 240px; height: 196px;" />
The resulting tree is shown above. This is the only valid operation that can be performed, but the resulting tree is not a valid BST, so return null.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/d3.png" style="width: 430px; height: 168px;" />
<pre>
<strong>Input:</strong> trees = [[5,4],[3]]
<strong>Output:</strong> []
<strong>Explanation:</strong> It is impossible to perform any operations.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == trees.length</code></li>
	<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
	<li>The number of nodes in each tree is in the range <code>[1, 3]</code>.</li>
	<li>Each node in the input may have children but no grandchildren.</li>
	<li>No two roots of <code>trees</code> have the same value.</li>
	<li>All the trees in the input are <strong>valid BSTs</strong>.</li>
	<li><code>1 &lt;= TreeNode.val &lt;= 5 * 10<sup>4</sup></code>.</li>
</ul>

from typing import List, Optional


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


class Solution:
    def __init__(self):
        self.blacklist = set()
        self.value2node = {}
        self.operation_count = 0

    def find_leaf(self, node, root):
        if not node:
            return
        """
        Needs to make sure the only root node doesn't get count as a leaf
        """
        if not node.left and not node.right and node != root:
            self.blacklist.add(node.val)
        self.find_leaf(node.left, root)
        self.find_leaf(node.right, root)

    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:
        """
        1. Find the root for the final BST:
            blacklist: all the leaf nodes
            whitelist: all the root nodes

            This root node is unique. 

            Assume there are two nodes which are both roots, but neither of them exist in the leave nodes. 
                Let's say A is the final root and B is also can be the root(not exist in the leave nodes), the
                subtree with B as the root will not be able to merge into the final tree, but the problem require
                n - 1 operations for n trees, so all the subtree needs to be merged into the final big tree

        2. build tree while checking if the bst is valid
            use recursive to return the validness of the bst
        3. Make sure all the tree have been used by count the times of merge operation and compare with the count of the trees
        """
        root_count = 0
        return_root = None

        for root in trees:
            self.find_leaf(root, root)

        for root in trees:
            if root.val not in self.blacklist:
                return_root = root
                root_count += 1
            self.value2node[root.val] = root

        # print(self.blacklist)
        # print(return_root)
        # print(self.value2node.keys())

        if root_count != 1:
            return None

        ok = self.build(return_root, float('-inf'), float('inf'), None, '')
        print(ok)
        print(self.operation_count)
        if ok and len(trees) - 1 == self.operation_count:
            return return_root
        else:
            return None

    def build(self, node, min_v, max_v, parent, d) -> bool:
        if not node:
            return True

        # print(min_v)
        # print(node.val)
        # print(max_v)

        if node.val <= min_v or node.val >= max_v:
            return False

        if node.left or node.right:
            return self.build(node.left, min_v, node.val, node, 'left') and self.build(node.right, node.val, max_v,
                                                                                       node, 'right')
        elif not node.left and not node.right and node.val in self.value2node:
            if d == '':
                """
                When the root passed in with no direction, should just return True for this subtree
                """
                return True
            self.operation_count += 1
            # print(node.val)
            if d == 'left':
                parent.left = self.value2node[node.val]
                node = parent.left
                return self.build(node.left, min_v, node.val, node, 'left') and self.build(node.right, node.val, max_v,
                                                                                           node, 'right')
            elif d == 'right':
                parent.right = self.value2node[node.val]
                node = parent.right
                return self.build(node.left, min_v, node.val, node, 'left') and self.build(node.right, node.val, max_v,
                                                                                           node, 'right')
        else:
            return True
1379