mysql - 查找具有 0 或 1 个子树的子树中的所有节点

Question

在我需要处理的事情中，在给定的时间，我需要找到树的所有节点(使用物化路径 + 相邻节点制作)有 0 或 1 个子节点。 这些列是这样的:

id int  
parent_node int  
treepath VARCHAR(255)  
deepness int

当我尝试为此提出解决方案时，我只能想到会使用太多子查询或表连接的非常复杂的查询。

对于有 0 个子节点的节点，我一直在考虑搜索所有未被 parent_id 引用且在子树中的节点。

SELECT *
FROM user_tree
WHERE
    node_id NOT IN (
        SELECT parent_id
        FROM user_tree
        WHERE parent_id IS NOT NULL
    )
    AND
    treepath LIKE 
        (
            SELECT CONCAT(treepath, '/%')
            FROM user_tree
            WHERE node_id = 4
        ) 

使用 EXPLAIN，从获取节点列表所需的时间来看，这对于 DB 来说似乎有点痛苦。

是否有一种非非常痛苦的方式(在性能方面)来进行查询以找到我想要的内容？

编辑:
根据要求，这里是表格的一些示例格式:

id      parent_id   treepath    deepness
1       NULL        1           0
2       NULL        2           0
3       1           1/3         1
4       1           1/4         1
5       4           1/4/5       2
7       3           1/3/7       2
8       3           1/3/8       2
9       7           1/3/7/11    3

Answer 1

没有样本数据，这只是一个猜测:

SELECT t1.*, t2.numchildren
FROM user_tree t1
LEFT JOIN ( SELECT parent_id, COUNT(*) AS numchildren
            FROM user_tree
            GROUP BY parent_id ) t2
ON t1.id = t2.parent_id
WHERE t2.numchildren IS NULL
OR t2.numchildren = 1;

SQL-Fiddle from sample data