文章目录

1. 题目2. 解题思路3. 代码实现3.1 解法一 4. 总结5. 参考文献

1. 题目

给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？数中节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。

例如，二叉树的中序遍历是{d, b, h, e, i, a, f, c, g}。该二叉树如下图所示：

a b c d e h i f g

2. 解题思路

针对不同位置的节点，分析逻辑。

因为中序遍历是根->左->右。 a. 当节点有右子树时，下一个节点就是右子树中的最左节点 当节点无右子树时，需要当前节点是其父节点的左子节点还是右子节点； b. 若是左子节点，那么下一个节点是节点的父节点。 c. 若是右子节点，那么下一个节点是为某个节点左子节点的祖宗节点的父节点。 d. 如果不存在c中那样的节点，则说明二叉树遍历完成了。

3. 代码实现

python中二叉树的节点：

class BinaryTreeNode: """定义二叉树节点""" def __init__(self, value, left_child=None, right_child=None, parent=None): self.value = value self.left = left_child self.right = right_child self.parent = parent

3.1 解法一

思路1的代码实现：

class Solution: def get_next(self, pNode): """获取二叉树中指定节点在中序遍历时的下一个节点 step1：当前节点是否有右子树 step2：当前节点是否处于左子树中 :param pNode: 指定的节点 :return pNext: 指定节点在中序遍历时的下一个节点 """ pNext = None # 边界条件 if not pNode: return if pNode.right: # 存在右子树 cur = pNode.right while cur.left: cur = cur.left pNext = cur elif pNode.parent: if pNode == pNode.parent.left: pNext = pNode.parent else: # 为右子树中的节点且自己没有右子树 pCurrent = pNode while pCurrent.parent: if pCurrent == pCurrent.parent.left: pNext = pCurrent.parent break pCurrent = pCurrent.parent return pNext

对比一下作者的逻辑（下面）和自己的，发觉还是写的太冗余了，一点都不pythonic。

class Solution: def get_next(self, pNode): """获取二叉树中指定节点在中序遍历时的下一个节点 step1：当前节点是否有右子树 step2：当前节点是否处于左子树中 :param pNode: 指定的节点 :return pNext: 指定节点在中序遍历时的下一个节点 """ pNext = None # 边界条件 if not pNode: return if pNode.right: # 存在右子树 cur = pNode.right while cur.left: cur = cur.left pNext = cur elif pNode.parent: pCurrent = pNode pParent = pNode.parent while pParent and pCurrent == pParent.right: pCurrent = pParent pParent = pParent.parent pNext = pParent return pNext

4. 总结

主要考察对二叉树中序遍历是否熟悉，再者是否能考虑到多种不同位置的节点的下一个节点是谁。

如果在while循环中只有一个if判断，则将此判断条件直接写在while语句中更好，

5. 参考文献

[1] 剑指offer丛书 [2] 剑指Offer——名企面试官精讲典型编程题