剑指Offer08：二叉树的下一个节点

题目

题目地址：

https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

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

相关题目：

如果把中序遍历换成前序遍历和后续遍历呢？

思路

中序遍历：DBHEIAFCG

• 如果该节点不存在右子树

  • 该节点为父节点的左子节点，则下一个节点就是它的父节点
  • 该节点为父节点的右子节点，沿着该节点的父节点往上遍历，直到找到一个是它父节点的左子节点的节点，如果找到这样的节点，那么这个节点的父节点就是我们要找的下一个节
  • 举例：
    • F 节点不存在右子树，该节点为父节点C的左子节点，则下一个节点为它（F）节点的父节点 C
    • G 节点不存在右子树，该节点为父节点C的右子节点，则在该节点（G）的父节点（C）往上遍历，C是是其（C）节点的右子节点，再往上遍历到 A，由于A 是树的根节点，没有父节点，所以G 没有下一个子节点

• 如果该节点存在右子树

  • 右子树存在左节点，则下一个节点为右子树的最左子节点
  • 右子树不存在左节点，则下一个节点为右子树
  • 举例：
    • B 节点存在右子树，右子树左节点 H，B的下一个节点为B的右子树的最左节点 H
    • E 节点存在右子树，右子树不存在左节点，则 E的下一个子节点为右子树 I

代码

边界条件

测试用例

• 普通二叉树（完全二叉树、不完全二叉树）
• 特殊二叉树（所有节点都没有右（左）子节点的二叉树，只有一个节点的二叉树，二叉树的根节点为空）
• 不同位置的下一个节点（当前节点没有下一个节点（如 G））

# -*- 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
        target = None
        if pNode is None:
            return target
        # 如果该节点不存在右子树
        #    该节点为父节点的左子节点，则下一个节点就是它的父节点
        #    该节点为父节点的右子节点，沿着该节点的父节点往上遍历，直到找到一个是它父节点的左子节点的节点，如果找到这样的节点，那么这个节点的父节点就是我们要找的下一个节
        if pNode.right is None:
            pCur = pNode
            father = pCur.next
            while father is not None:
                if father.left is not None and father.left == pCur:
                    return father
                pCur = father
                father = pCur.next
            return target
        # 如果该节点存在右子树
        #    右子树存在左节点，则下一个节点为右子树的最左子节点
        #    右子树不存在左节点，则下一个节点为右子树
        pCur = pNode.right
        while pCur is not None:
            if pCur.left is not None:
                pCur = pCur.left
            else:
                target = pCur
                break;
        return target