返回正好低于

Question

我有一棵普通的树，看起来像这样：

我想写一个函数MyFunc（tree，tree\u element） 将返回元素的父级。但不是直接父级，而是正好在根下一级的父级。 如果是附着的树：

MyFunc(tree,'Dasani')

将返回“Coke”，同时：

MyFunc(tree,'Zero Sugar')

将返回“百事可乐”

我能写两个函数。 First返回直接父级：

class tree:
    def __init__(self, key):
            self.data = key
            self.left = None
            self.right = None

    def parent_search(self, root, child_node):
        if  root :
            if root.left and root.left.data== child_node:
                return root.data
            if root.right and root.right.data== child_node:
                return root.data
            elif root:
                return self.parent_search(root.left, child_node) or self.parent_search(root.right, child_node)

root = tree('Beverage') 
root.left = tree('Pepsi') 
root.right = tree('Coke') 
root.left.left = tree('Zero Sugar') 
root.left.right = tree('Cherry Pepsi') 
root.right.left = tree('Sport Drinks')
root.right.left.left = tree('Powerade')
root.right.left.right = tree('Dasani')
root.right.left.left.left = tree('Powerade w/Sugar')

print(root.parent_search(root,'Dasani'))

第二个返回到根的整个路径：

def printAncestors(root, target): 

    if root == None: 
        return False 

    if root.data == target: 
        return True 

    if (printAncestors(root.left, target) or 
        printAncestors(root.right, target)): 
        print root.data, 
        return True

     return False
printAncestors(root, 'Dasani')

但是，我需要介于两者之间的东西，它只返回一个元素，而这个元素正好在根下一级。 我能计算出这棵树从叶子到树根的高度。然后我想返回一个元素，它的高度是叶子上方的1，但我不确定这是正确的方法。你知道吗

Answer 1

一种方法是将到根的路径传递到每个递归级别，然后返回整个路径，然后可以提取所需路径的任何部分，如：

代码：

def parent_search(self, child_node, path_so_far=()):
    path_so_far += self.data,
    if (self.left and self.left.data == child_node or
            self.right and self.right.data == child_node):
        return path_so_far
    return (
        self.left and self.left.parent_search(child_node, path_so_far) or
        self.right and self.right.parent_search(child_node, path_so_far)
    )

测试代码：

class Tree:
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None

    def parent_search(self, child_node, path_so_far=()):
        path_so_far += self.data,
        if (self.left and self.left.data == child_node or
                self.right and self.right.data == child_node):
            return path_so_far
        return (
            self.left and self.left.parent_search(child_node, path_so_far) or
            self.right and self.right.parent_search(child_node, path_so_far)
        )


root = Tree('Beverage')
root.left = Tree('Pepsi')
root.right = Tree('Coke')
root.left.left = Tree('Zero Sugar')
root.left.right = Tree('Cherry Pepsi')
root.right.left = Tree('Sport Drinks')
root.right.left.left = Tree('Powerade')
root.right.left.right = Tree('Dasani')
root.right.left.left.left = Tree('Powerade w/Sugar')

print(root.parent_search('Dasani'))
print(root.parent_search('Dasani')[1])

结果：

('Beverage', 'Coke', 'Sport Drinks')
Coke