二叉树查找后继节点(即中序遍历情况下的这个节点的下一个) Python实现，,1.若节点类型没有p

二叉树查找后继节点(即中序遍历情况下的这个节点的下一个) Python实现，,1.若节点类型没有p

1.若节点类型没有parent属性，采用中序遍历方式获取后继节点

 1 def getSuccessorNode(head, node): 2     if (not node) or (not head): 3         return None 4     stack = [] 5     flag = False 6     while head or len(stack) > 0: 7         if head: 8             stack.append(head) 9             head = head.left10         else:11             head = stack.pop()12             if flag:13                 return head14             if head == node:            # 若找到当前节点，则下一个弹出的节点即为后继节点15                 flag = True16             head = head.right17     return None

2.若节点存在parent属性即

 1 class TreeNode: 2     def __init__(self, x=0): 3         self.val = x 4         self.parent = None 5         self.left = None 6         self.right = None 7  8  9 def getSuccessorNode(node):10     if not node :11         return None12     if node.right:               # 如果当前节点有右子树，则返回右子树的最左边节点13         node = node.right14         while node.left:15             node = node.left16         return node17     else:                        # 没有右子树   则向上找寻父节点，直到为父节点的左子树，返回父节点，否则返回空18         par = node.parent19         while not par and par.left != node:20             node = par21             par = par.parent22         return par

二叉树查找后继节点(即中序遍历情况下的这个节点的下一个) Python实现