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

Solutions

  分三个情况讨论每个情况的下一个结点。

# -*- coding:utf-8 -*-
# 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 pNode is None:
            return 
        # 如果结点存在右子树,那么下一个结点是右子树最左节点
        elif pNode.right is not None:
            pNode = pNode.right
            while pNode.left is not None:
                pNode = pNode.left
            return pNode
        # 如果一个结点没有右子树,且它还是其父节点的右子树,那么下一个结点就是父节点
        elif pNode.next is not None and pNode.next.right is pNode:
            while pNode.next is not None and pNode.next.left != pNode:
                pNode = pNode.next
            return pNode.next
        # 如果一个结点是其父节点的左子结点,直接返回其父节点
        else:
            return pNode.next
# 运行时间:29ms
# 占用内存:6620k

References

  1. 058. 二叉树的下一个结点