博客

一开始，自己走了弯路，也不知道怎么分类讨论，虽然最后总是把所有情况都凑完整了，思路还是很混乱。好像用不了递归，也可能是本人所学有限，发散思维不够。所以在做完之后，自己再一次整理了解题的逻辑，总结如下：

思路

：根据中序遍历的逻辑，主要讨论所给子树根结点是否有右孩子，所以大概分为以下情况讨论：

一、子树根结点有右孩子，则

返回右孩子或者右孩子中序遍历的前一个结点

二、子树根结点没有右孩子，分下列情况讨论：

1. 子树根结点有父节点（这时候就主要看它是父结点的左子树还是右子树了）
   
   (1)是父结点的左子树，则
   
   返回父结点
   
   
   (2)是父结点的右子树，看看是不是在左分支上

   • 在左分支上，则
     
     返回左分支的父结点
     

   • 不在，也就是整个二叉树只有右孩子，并且所给子树根结点是唯一一个叶子结点，那么
     
     返回None
     

2. 子树根结点没有父节点，
   
   返回None
   

python代码如下

：

# -*- 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 not pNode:
            return None
        if pNode.right != None:
            return pNode.right if not self.GetPre(pNode.right) else self.GetPre(pNode.right)
        else:
            if pNode.next == None:
                return None
            else:
                if pNode.next.left == pNode:
                    return pNode.next
                else:
                    c = pNode.next
                    f = c.next
                    while f != None:
                        if f.left == c:
                            return f
                        c = f
                        f = c.next
                    return None

    def GetPre(self, node):
        if node.left == None:
            return None
        else:
            k = node.left
            v = k.left
            while v != None:
                k = v
                v = k.next
            return k