如何获取二叉树中最后未填充节点的引用以实现新节点插入？

嘿，你问的这个问题，其实核心场景一般是完全二叉树的插入操作（毕竟只有这种结构才有明确的“最后一个未填充节点”的定义）。下面给你两种好用的定位思路：

方法一：层次遍历（广度优先搜索） #

这是最直观的方法，按层遍历整个树，找到第一个有空缺孩子的节点：

• 先准备一个队列，把根节点放进去
• 循环从队列里取出节点：
  • 如果当前节点的左孩子是空的，那它就是目标节点，新值直接插在左孩子位置
  • 如果左孩子存在，但右孩子是空的，这个节点就是目标，新值插在右孩子位置
  • 如果左右孩子都有，就把这两个孩子依次加入队列，继续往下找
• 直到找到符合条件的节点为止

给你一段伪代码参考：

def find_target_node(root):
    if not root:
        return None
    node_queue = [root]
    while node_queue:
        current_node = node_queue.pop(0)
        # 左孩子为空，直接返回当前节点
        if not current_node.left:
            return current_node
        # 右孩子为空，返回当前节点
        if not current_node.right:
            return current_node
        # 左右都有，加入队列继续遍历
        node_queue.append(current_node.left)
        node_queue.append(current_node.right)
    return None

这个方法逻辑简单，不管树是不是完全二叉树都能用，但在完全二叉树场景下效率也很高。

方法二：利用完全二叉树的数组存储特性 #

如果你的完全二叉树是用数组来存储的（完全二叉树天生适合这种存储方式），那定位会更高效，直接用索引就能算出来：

• 完全二叉树的数组存储规则：索引为i的节点，左孩子索引是2*i+1，右孩子是2*i+2；反过来，任意节点的父节点索引是(i-1)//2
• 假设当前数组里已经有n个节点，新插入节点的索引就是n，它的父节点就是索引(n-1)//2对应的节点
• 这个父节点就是你要找的“最后一个未填充节点”，新值要么是它的左孩子，要么是右孩子（完全二叉树是从左到右填充的，所以一定是先填左再填右）

举个例子：如果数组里现在有5个节点（索引0到4），新节点索引是5，父节点索引是(5-1)//2=2，这个父节点就是目标节点，新值插在它的左孩子位置就行。
这个方法的时间复杂度是O(1)，但只适用于完全二叉树的数组存储结构，效率拉满。

内容的提问来源于stack exchange，提问作者Марк Павлович