求出完全二叉树T中编号i和j的两个结点的最近公共祖先结点的编号的方法

在完全二叉树 T 中，寻找编号为 i 和 j 的节点的最近公共祖先 (LCA) 可以通过一些高效的算法实现，如层次遍历、递归或者自底向上的迭代。这里我们可以使用递归方法：

1. **递归法**：假设根节点的编号为 1，对于任意两个节点，它们的 LCA 可能在它们各自路径上最高的公共节点。从根节点开始，分别查找路径至节点 i 和 j，如果在相同的高度上遇到，则这个节点就是 LCA。如果 i 的路径更长，继续沿着 j 的路径向上查找；反之亦然。

   def lca(root, i, j):
       if not root or root.val == i or root.val == j:
           return root.val
       if root.val > min(i, j):  # 如果当前节点大于最小值，说明应该往上走
           return lca(root.left, i, j)
       else:
           return lca(root.right, i, j)

2. **迭代法（使用栈）**：可以先将 i 和 j 的路径压入栈中，然后逐层比较，当找到相同节点时，即找到了 LCA。

- 初始化两个指针分别指向 i 和 j 的路径，同时创建一个空栈。
- 当两者的路径未结束时，每次取出节点进行比较，如果在栈顶的节点相等，返回该节点；否则将较小路径的下一个节点压入栈。

注意，这种方法的时间复杂度通常是 O(log n)，其中 n 是树的高度，因为二叉树的高度决定了需要比较的最大层数。