我有一个简单的二叉树，我正在试图找到的最后一个节点

Question

findlast func正在返回正确的节点（在返回之前检查了值），但是名为lastnode的接收节点变为none

只需返回树的最后一个节点，然后用这个节点替换要删除的节点

class tree:
    def __init__(self):
        self.root=None 

    def findlast(self,node,arr):
        if(node.left!=None):
            arr.append(node.left)
        if(node.right!=None):
            arr.append(node.right)
        if(len(arr)==1):
                print(arr[0].data)  #prints 3
                return arr[0]
        elif(self.root==None and len(arr)==0):
            print("empty tree")
        elif(self.root!=None and len(arr)==0):
            return self.root
        else:
            self.findlast(arr.pop(0),arr)


class treeNode:

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

bst=tree()
tn1=treeNode(2)
tn2=treeNode(3)
bst.root=treeNode(1,tn1,tn2)
arr=list()
print(bst.findlast(bst.root,arr).data)   #throws error "nonetype has no object data" 

Answer 1

要在最低级别找到最右边的节点，请按顺序遍历树。当你找到一个叶子节点时，对照你以前找到的最深的节点检查它的深度。如果新节点的深度大于或等于前一个最深节点，则新节点将成为最深节点。这是因为按顺序遍历树将从左到右访问叶节点

这是一个O（n）操作。因为必须遍历整个树才能找到最深的节点，所以不可能再快一点