面试题8：二叉树的下一个节点

题目描述

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

知识点

二叉树的遍历

Qiang的思路

对于该问题，想要去找二叉树中一个节点在中序遍历时的下一个节点，首先应该清楚二叉树的中序遍历是怎么回事。二叉树的中序遍历是对二叉树进行遍历的一种方式，其顺序是首先遍历二叉树的左子树，然后是根节点（中序的中即根节点在中间被遍历），最后是二叉树的右子树。

在遍历过程中，对于一个刚被遍历之后的节点，下一步需要遍历的节点肯定是先去寻找该节点对应的右子树，因为把该节点作为其子树的根节点，那么遍历完根节点之后肯定是需要遍历右子树的。在这个地方就产生了问题。右子树存不存在呢？

显然，如果右子树存在，那么下一个被遍历的节点就应该是右子树的中序遍历的第一个元素，该元素也就是右子树最左下角的叶节点。于是我们可以依次寻找右子树的左子树，该左子树的左子树，...，直到找到叶子节点为止，该节点就是下一个要被遍历的节点了。

接下来讨论另外的一种情况，也是相对复杂的一种情况，就是当右子树不存在时如何进行寻找。当右子树不存在时就说明以刚被遍历的这个节点为根的子树已经被完全遍历了，下一步就要往其父节点出发了。但是，这时又存在了两种情况，万一父节点不存在呢，如果不存在就说明当前节点就是整个二叉树的根节点，现在整个树都已经遍历完成了，所以就没有必要继续遍历了，直接返回None就OK了。

另外一种情况：父节点是存在滴。那么这里又得分为两种情况继续讨论了（咋这么多情况）。一是当前节点是父节点的左孩子，第二种情况是右孩子。如果是左孩子那么就直接将父节点输出就行了，因为左子树遍历完了下一步肯定就是根节点嘛。

但如果当前节点是父节点的右孩子，这是表明其父节点为根的子树已经被完全遍历了，这时就需要再继续往上找，直到找到某个节点是其父节点的左孩子为止，此时将其父节点返回就OK了。当然，如果遍历到父节点为空了那就说明输入的节点就是整个二叉树中序遍历的最后一个节点了，那就直接返回None就可以了。

# -*- 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
        if pNode.right!=None:
            pNode=pNode.right
            while pNode.left!=None:
                pNode=pNode.left
            return pNode
        if pNode.next!=None:
            while pNode.next.right==pNode:
                pNode=pNode.next
                if pNode.next==None:
                    return None
            return pNode.next
        return None

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。