[剑指Offer]二叉树的下一个结点

题目描述

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

解题思路

分为两种情况:

  1. 该结点的右子树不为空,那么找到右子树的最左边的结点即为该结点的下一个结点,可用递归实现;
  2. 该节点的右子树为空,可以分为两种情况:
    1. 该节点是其父结点的左子结点,那么它的下一个结点为父结点;
    2. 该节点是其父结点的右子结点,则可沿着父结点的路径一直往上找,若找到某一结点为其父结点的左子结点,则该结点的父结点为原结点的下一个结点;若找到根结点(没有父结点的结点)都没有满足条件的,则说明原结点为最右的结点,其下一个结点为None

代码

Python(2.7.3)

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
# -*- 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 is None:
if pNode.next is None:
return
if pNode.next.left == pNode:
return pNode.next
while pNode.next.right == pNode:
if pNode.next.next is None:
return
pNode = pNode.next
return pNode.next
return self.GetLeft(pNode.right)

def GetLeft(self, root):
if root.left is None:
return root
return self.GetLeft(root.left)

运行时间:26ms
占用内存:5856k