题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
这道题的常规解法有两种
可以参考 这个解法
我的解法是递归解 但是不用存储二叉树的所有节点
利用状态码的思想.. 有这个思想吗？ 不知道，可能是自己瞎编的
class Solution:
def GetNext(self, pNode):
# write code here
if not pNode:
return
# 获得根节点
pRoot = pNode
while pRoot.next:
pRoot = pRoot.next
self.res = None
def inOrder(root, state):
if not root:
return state # 为啥不能是 return -1
state = inOrder(root.left, state)
if state == 1: #检查状态码
self.res = root # 必须定义为 self类的属性才有用
state = 2
if root == pNode: # 找到目标节点之后 将状态码置成1 下一次的判断到状态码为1的节点就是需要return的节点
state = 1
if state == 2: # 加速递归的结束 后面的节点不用继续递归
return state
state = inOrder(root.right, state)
return state
inOrder(pRoot, -1)
return self.res
大体的思想是：
- 找到根节点
- 利用中序遍历 参考代码注释吧 很详细了..
个人的第一篇博客
可能有点菜 各位大佬轻喷
