如何查找节点是否存在于二叉树中（按索引，而不是按值）？

Question

给定一个完整的二叉树，其中节点的索引从1到N（索引1是根，N是树中的节点数）。在O（logN）时间复杂度下，我们能发现树中是否存在具有特定索引的节点吗？

How is the indexing done?
for a node say it has      index x
                          /        \
             node.left is 2*x    node.right is 2*x+1

下面我写了在O（N）中运行的代码

当节点位于右子树深处时，O（N）解似乎效率很低。我们可以避免在根级别访问左子树吗？

利用O（logN）时间复杂度是一个完整的二叉树这一事实，有可能实现这一目标吗？

##TreeNode object
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

##findIndex
def findIndex(root,index,target):
    if root == None:
        return False
    if index == target:
        return True

    leftSide = findIndex(root.left,2*index,target)
    rightSide = findIndex(root.right,2*index+1,target)

    return (leftSide or rightSide)

##Create tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

"""
For the sake of simplicity, 
the tree node values are the same as their index.
                1
               /  \
             2     3
            / \  
           4   5
"""

##call findIndex

## findIndex(root, startIndex, targetIndex) 

print findIndex(root,1,1) ## returns True
print findIndex(root,1,8) ## returns False

Answer 1

使用堆栈：

1. 除以2，因为我们知道每个节点的索引是其父节点的两倍。如果父项为i，则左侧子项为2i，右侧子项为2i
2. 我们有一个索引，所以我们推动它的父对象从根到堆栈
3. 逐个从堆栈中移除，并根据奇偶性选择决策。最后，如果该节点存在，则表示树具有该节点

 private boolean nodeExist(TreeNode node, int idx){
        Stack<Integer> stack = new Stack<>();
        int temp = idx;
        while(temp !=1){
            stack.push(temp);
            temp /=2;
        }
        while(!stack.isEmpty()){
            if(stack.pop() %2 ==0){
                node = node.left;
            }else{
                node = node.right;
            }
        }
        
        return node !=null;
    }

Answer 2

因为我们已经知道左节点是2*n，右节点是2*n 1。让我们首先从输入中给定的索引开始，找出路径。例如，如果我们将索引设为10，那么我们知道10应该在5的左边，而5应该在2的右边，也就是根或1的左边。所以路径是左、右、左。现在，只要在二叉树中遍历这条路径，只要它的null（如果节点存在）返回true或false。