python实现二叉树题的相关代码-左程云视频笔记-更新中

左程云视频笔记和python实现
b站视频链接

二叉树

遍历

• 二叉树三种遍历方式

"先序遍历，先输出根，再遍历左，遍历右"
def preOrder(node):
    if node == None:
        return
    print(node.val)
    preOrder(node.left)
    preOrder(node.right)
"中序遍历，先遍历左，再输出，再遍历右"
def midOrder(node):
    if node == None:
        return
    preOrder(node.left)
    print(node.val)
    preOrder(node.right)
"后序遍历，先遍历左，遍历右，再输出"
def backOrder(node):
    if node == None:
        return
    preOrder(node.left)
    preOrder(node.right)
    print(node.val)

• 非递归实现

"非递归实现先序遍历，中序和后序也是类似"
def preOrderUnrecur(node):
    print("pre-order:")
    if node:
        stack = [node]          # python的列表可以当作栈
        while len(stack):       # 栈不空
            head = stack.pop()      # 弹出最后一个元素
            print(head.val,' ',end='')
            if head.right:
                stack.append(head.right)
            if head.left:
                stack.append(head.left)

寻找最近公共祖先

• 思路
• 代码

# o1,o2就是两个待寻找祖先的结点
def LowestAncestor(head,o1,o2):
    if head == None or head == o1 or head == o2:
        return head
    left = LowestAncestor(head.left,o1,o2)
    right = LowestAncestor(head.righr,o1,o2)
    # 如果左右子树都不为空，就返回自己
    if left and right:
        return head
    # 返回为空的另一个结点
    return left if left else right

给定结点，找后继结点

• 后继结点：中序遍历中，当前结点的下一个结点就称后继结点
• 结点结构体包括左孩子，右孩子，父亲，三个指针
• 代码

def getLeftMost(node):
    if node == None:
        return node
    while node.left != None:
        node = node.left
    return node

def getSuccessorNode(node):
    if node == None:
        return node
    if node.right != None:
        return getLeftMost(node.right)
    else:   # 无右子树
        parent = node.parent
        while parent != None and parent.left != node:
            node = parent
            parent = node.parent
        return parent