剑指offer 牛客网 二叉树的下一个节点
结合图，我们可发现分成两大类：
1、有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G）
2、没有右子树的，也可以分成两类，a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ； b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。
# -*- coding: utf-8 -*- """ Created on Wed Apr 10 10:52:32 2019 @author: Administrator 题目描述 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 思路： 中序遍历的规则是：左根右 分析二叉树的下一个节点，一共有以下情况： 1.二叉树为空，则返回空； 2.节点右孩子存在，则设置一个指针从该节点的右孩子出发， 一直沿着指向左子结点的指针找到的叶子节点即为下一个节点； 3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点； 否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。 """ # -*- coding:utf-8 -*- class TreeNode: 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 pNode if pNode.right: #假如有右节点，则下个节点是右孩子的左子节点 node = pNode.right while node.left: #直到遇左节点为空便返回 node = node.left return node while pNode.next: #去寻找父亲节点 temp = pNode.next if temp.left == pNode: #直到左孩子是其节点便返回 return temp pNode = temp if __name__ == '__main__': solution = Solution() #1 2 3 4 5 6 7 8 9 #根节点是4 n = TreeNode(9) node = TreeNode(8) node_left = TreeNode(1) node_right = TreeNode(3) node.left = n node_left.left = node root_left = TreeNode(2) root_left.left = node_left root_left.right = node_right node_left = TreeNode(5) node_right = TreeNode(7) root_right = TreeNode(6) root = TreeNode(4) root.left = root_left root_right.left = node_left root_right.right = node_right root.right = root_right res = solution.GetNext(root) print(res.val) #5