二叉树条件插入：如何单次遍历实现去重插入与计数更新

核心实现逻辑是把查找、计数、插入三个动作合并到同一次树遍历路径中，利用递归返回值挂载新节点，匹配到重复值时直接终止遍历更新计数，全程只需要从根节点走到目标位置一次，时间复杂度为O(h)（h为树高），完全避免两次遍历的额外开销。

实现关键点 #

• 遍历到Id匹配的节点时，直接将节点的NodeCounter加1，立刻返回当前节点终止当前分支遍历，不会触发重复计数
• 遍历到空节点位置时，说明树中不存在待插入Id，直接初始化新节点返回，上层递归会自动将新节点挂载到父节点的对应左/右分支
• 每一层递归处理完子节点逻辑后，都返回当前节点，保证原有树结构不会被破坏

递归实现代码 #

class BinTree:
    def __init__(self, Id):
        self.Id = Id
        self.NodeCounter = 1
        self.left = None
        self.right = None

    def insert(self, target_id):
        # 匹配到重复节点，直接更新计数后返回
        if self.Id == target_id:
            self.NodeCounter += 1
            return self
        
        # 目标Id更小，递归处理左子树
        if target_id < self.Id:
            if self.left is None:
                # 左子树为空，直接挂载新节点
                self.left = BinTree(target_id)
            else:
                # 左子树非空，继续向下遍历，用返回值更新左子节点指针（不影响原有结构）
                self.left = self.left.insert(target_id)
        # 目标Id更大，递归处理右子树
        else:
            if self.right is None:
                self.right = BinTree(target_id)
            else:
                self.right = self.right.insert(target_id)
        
        # 返回当前节点供上层挂载
        return self

常见计数错乱原因 #

之前合并遍历出现计数错误，基本都是两个原因导致的：

1. 匹配到重复节点后没有提前终止递归，继续向下遍历走到了新插入的节点位置，导致计数被多加
2. 插入新节点后没有正确将节点挂载到父节点的对应分支，导致树结构断裂，后续遍历重复触发计数逻辑

非递归（迭代）实现 #

如果不想用递归，也可以用指针跟踪当前遍历位置，单次遍历完成所有逻辑，避免递归栈开销：

def insert_to_tree(root, target_id):
    # 空树直接返回新节点作为根
    if not root:
        return BinTree(target_id)
    
    current = root
    while True:
        # 匹配到重复节点直接更新计数返回
        if current.Id == target_id:
            current.NodeCounter += 1
            return root
        # 走左子树
        if target_id < current.Id:
            if not current.left:
                current.left = BinTree(target_id)
                return root
            current = current.left
        # 走右子树
        else:
            if not current.right:
                current.right = BinTree(target_id)
                return root
            current = current.right

注意事项 #

以上实现默认你构建的是按Id排序的二叉搜索树，如果你的二叉树没有固定的左右子树排序规则，不存在有序排列的前提，那单次遍历无法覆盖所有节点查找重复值，这种场景下两次遍历是必要的。

内容的提问来源于stack exchange，提问作者Rahul Kumar