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

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) 时间复杂度内实现 objective？

##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

因为我们已经知道左节点是2*n，右节点是2*n + 1。让我们先从输入中给定的索引开始，找出路径。例如，如果我们的索引为 10，那么我们知道 10 应该在 5 的左边，而 5 又应该在 2 的右边，也就是 root 或 1 的左边。所以路径是左，右，左。现在，只要在二叉树中遍历此路径，如果节点存在则为 null return true else false.

Answer 2

使用堆栈：

除以 2，因为我们知道每个节点的索引是其 parent 的两倍。如果parent是i，左边的child是2i，右边的child是2i+1.
我们有一个索引，所以我们将它的 parent 推到根堆栈。
一张一张地从堆叠中取出，然后选择decision-based奇数和偶数。最后，如果该节点存在，则表示树有该节点。

 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;
    }

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

How to find if a node exists in the binary tree or not (by index, not by value)?

binary-tree

data-structures