在二叉树中查找未暴露的节点

Question

如何在二叉树中找到未暴露的节点。当我说非暴露节点时，我的意思是从树的顶部、底部、左侧和右侧覆盖节点

含义：
当一个节点在顶部未暴露时：它有一个父节点
当一个节点在底部未暴露时：它至少有一个子节点
当节点在左侧（或右侧）未暴露时：在给定节点的左侧（或右侧）至少有一个节点处于同一水平标高

注意：树不一定是一个完整的二叉树

Answer 1

您可以使用宽度优先搜索按级别查找所有节点，然后从非父级或叶级中选择节点，这些节点由左右两侧的节点缓冲：

from collections import deque, defaultdict
def non_exposed(tree):
   d, q = defaultdict(list), deque([(0, tree)])
   while q:
      d[(v:=q.popleft())[0]].append(v[1])
      q.extend([*filter(lambda x:x[-1], [(v[0]+1, v[1].left), (v[0]+1, v[1].right)])])
   return [j for a, b in d.items() for j in b[1:-1] if a and any([j.left, j.right])]

---

演示：

import random
class Tree:
   def __init__(self, v, left = None, right = None):
      self.v, self.left, self.right = v, left, right
   def __repr__(self):
      return f'Tree({self.v}, {self.left}, {self.right})'

def get_tree(n):
   v = random.randint(1, 10)
   return None if not n else Tree(v, left=get_tree(n-1), right=get_tree(n-1))

test_tree = get_tree(5)
results = [i.v for i in non_exposed(test_tree)]
print(len(results))

输出：

8

说明：

get_tree构建一个完整的n级别的“二叉”树。在这样的树中，完整节点的总数将为sum(pow(2, i) - 2 for i in range(2, n-1))，因此在n=5时给出8的结果