剑指57-二叉树的下一个结点

Posted on | In |

题目描述

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

画出一个二叉树的图来帮助分析，分两种情况：

  • pNode有右子树，下一个节点肯定在右子树上。具体来说，在其右子树上一直迭代找到最后一个左孩子。
  • pNode无右子树，下一个节点得往回查。具体来说，查到某个父节点是祖节点的左孩子。如果这个祖节点存在，那么它就是下一个节点。如果不存在，pNode就是二叉树的中序遍历的最后一个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def GetNext(self, pNode):
        if pNode.right: # pNode有右子树，下一个节点肯定在右子树上
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        # 无右子树，下一个节点得往回查
        # pNode是父节点的左孩子，则下一个节点是其父节点
        # pNode是父节点的右孩子，就麻烦了。先往回查，直到某个父节点是祖节点的左孩子
        while pNode.next and pNode != pNode.next.left:
            pNode = pNode.next
        return pNode.next