二叉树的下一个节点

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

题目给出的默认代码为：

 1 # -*- coding:utf-8 -*-
 2 # class TreeLinkNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 #         self.next = None
 8 class Solution:
 9     def GetNext(self, pNode):
10         # write code here

这里开始我就没有理解题目的意思，认为题目应该给出两个参数，一个二叉树，一个结点。而且定义中的next也模糊。后来发现next就是指的parent，就是父结点。

思路：题目已给出了当前结点，我们要做的是通过给出的当前结点找到他中序遍历的下一个结点，由于定义中每一个结点都包含其左右结点以及父结点的指针，所以我们就可以通过当前结点找出其他结点的信息。

首先知道中序遍历的规则是：左根右，然后作图

二叉树的下一个节点

结合图，我们可发现分成两大类：1、有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G） 2、没有右子树的，也可以分成两类，a)是父节点左孩子（eg：N，I，L），那么父节点就是下一个节点； b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。

Python代码如下

 1 # -*- coding:utf-8 -*-
 2 # class TreeLinkNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 #         self.next = None
 8 class Solution:
 9     def GetNext(self, pNode):
10         # write code here
11         if not pNode:
12             return pNode
13         if pNode.right:#右子树不为空
14             pNode = pNode.right
15             while pNode.left:
16                 pNode = pNode.left
17             return pNode
18         while pNode.next:#非根结点
19             if pNode == pNode.next.left:
20                 return pNode.next
21             pNode = pNode.next
22         return None

二叉树的下一个节点

相关推荐