算法设计

剑指offer之057-二叉树的下一个结点

作者明柳梦少，发布于 。

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode: return None
        p = pNode
        if pNode.right:  # 有右子树
            p = pNode.right
            while p.left:
                p = p.left
            return p
         # 没有右子树但是有父亲节点
        while pNode.next and pNode.next.right == pNode:
            pNode = pNode.next
        return pNode.next
隐藏作者信息

关于明柳梦少

坚守自己的原则，不随波逐流。