Sword_Offer 二叉树的下一个节点[8]

Sword_Offer 二叉树的下一个节点[8]

0x00 题目描述

题目：给定一棵二叉树和其中的一个节点,如何找出中序遍历序列的下一个节点？

0x01 解题思路

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# Author LQ6H

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

class Solution:
    def GetNext(self,pNode):
        """
        :param pNode: TreeNode
        :return: TreeNode
        """
        if not pNode:
            return None
        
        if pNode.right:
            p_right=pNode.right
            
            while p_right.left:
                p_right=p_right.left
            return p_right
        
        while pNode.next:
            pp=pNode.next
            if pp.left==pNode:
                return pp
            pNode=pp