[剑指Offer] 08_二叉树中的下一个节点

题目

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

例:

注：1,2,3,4,5,6,7,8,9 = a,b,c,d,e,f,g,h,i
中序遍历为{d, b, h, e, i, a, f, c, g}
输入b输出h，输入i输出a

思路

1. 中序遍历的输出顺序是左子树-根-右子树。因此下一个节点一定是右子树中的最左节点。
   1. 该节点存在，则输出该节点。[情况1]
   2. 该节点不存在。则该层次已经遍历完毕，返回上一级遍历。
      1. 当前节点在父节点的左子树中。[情况2] 输出其父节点。
      2. 当前节点在父节点的在右子树中。[情况3] 继续返回上一级，直到出现情况2。如果返回到根节点都没有出现情况2，则表明已经输出全部节点，中序遍历完成。

• 时间复杂度：最差情况出现在只有右树时，需要输出最右节点的下一节点。O(n)
• 空间复杂度：O(1)

代码

思路1：时间复杂度O(n)，空间复杂度O(1)

class TreeNode(object):

    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.parent = None


def next_node_in_binary_trees(cur_n):
    """
    :param cur_n: current node
    :return:inoreder next node
    """
    if not cur_n:
        return 'EMPTY INPUT'
    if cur_n.right:
        next_n = cur_n.right
        while next_n.left:
            next_n = next_n.left
    else:
        if not cur_n.parent:
            return None
        if cur_n.parent.left == cur_n:
            next_n = cur_n.parent
        else:
            next_n = cur_n.parent
            while next_n.parent and next_n.parent.left != next_n:
                next_n = next_n.parent
            else:
                next_n = next_n.parent
    return next_n

思考

准备把前序、中序、后序的递归和迭代都实现一下，加深理解。
本题的测试用例没有自动生成，可以考虑写一个list to TreeNodeWithParent。自动从list构建二叉树。