题目描述

[牛客网)]

08. 二叉树的下一个结点

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

解法 1:递归

中序遍历的顺序是 -> -> ,假设我们已知结点 N,要找中序遍历顺序下 N 的下一个结点,我们查找的顺序如下:

  1. N 有没有右子结点,有则返回 N 的右子树在中序遍历顺序下的下一个结点,否则进入下一步;
  2. N 有没有父结点,没有则返回空,否则进入下一步;
  3. N 是否是其父结点的左子结点,若是则返回 N 的父结点,否则进入下一步;
  4. N 是否是其父结点的右子结点,若是则沿着父结点往上遍历,相当于砍断 N 与父结点的联系,然后找中序遍历顺序下 N 的父结点的下一个结点(形成了递归)。
  5. 重复以上 4 步,直到返回。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# -*- 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):
        curr = pNode

        # Go into right subtree
        if curr.right is not None:
            curr = curr.right
            while curr.left is not None:
                curr = curr.left
            return curr

        # Parent node is None
        if curr.next is None:
            return None

        # Curr is parent node's left child
        if curr == curr.next.left:
            return curr.next

        # Curr is parent node's right child
        curr = curr.next
        curr.right = None
        return self.GetNext(curr)
  • 运行时间:25ms
  • 占用内存:5864k

解法 2:迭代且不修改原二叉树

上一种解法虽然解决了问题,但是其实存在冗余的地方可以优化(第 3、4 步),并且最后的递归过程修改了输入的二叉树,这很不好。

思考一下,当我们退回到 N 的父结点(记为 M)的时候,要找的是什么。如果 M 是其父结点的左子结点,那么返回 M 的父结点即可;如果 M 是其父结点的右子结点,那么我们又退回到 M 的父结点。其实这一步是循环的。

通过这里的优化,我们可以将解法 1 末尾的递归改成循环,并且不需要修改原来的二叉树了,代码也简洁了一些。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# -*- 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):
        curr = pNode

        # Go into right subtree
        if curr.right is not None:
            curr = curr.right
            while curr.left is not None:
                curr = curr.left
            return curr

        # Return to parent node
        while curr.next is not None:
            if curr == curr.next.left:
                return curr.next
            curr = curr.next
        return None
  • 运行时间:25ms
  • 占用内存:5856k