塞进裤子ヾ(≧O≦)〃嗷~

0%

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

一开始没懂题目什么意思。就是给二叉树的一个结点A,这个结点除了左右孩子指针还有个父节点指针,求二叉树中序遍历后A节点的下一个结点,返回它。

最初想法:

复原这棵二叉树,求出此二叉树的中序遍历,得到A的下一个结点的元素值,但不知道怎么返回这个结点。

看了别人的代码,是在中序遍历过程中将每个节点保存到一个list中。

(我想的是记录value值比较value,但无法处理值相同的情况,没想到可以保存节点类型到list中)。

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
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
#找到根节点
myroot= pNode
while myroot.next:
myroot = myroot.next
self.nodeList = [] #存储中序遍历的节点
self.inorder(myroot)

myIndex = self.nodeList.index(pNode)+1 #下一个节点的索引
if myIndex != len(self.nodeList):
return self.nodeList[myIndex]
else:
return None

def inorder(self, rootNode):
# 中序遍历
if rootNode is None:
return
self.inorder(rootNode.left)
self.nodeList.append(rootNode)
self.inorder(rootNode.right)

method2:直接由这个结点推出中序遍历中下一个结点

分两种情况,设给的结点为A,一是A有孩子,二是A没有孩子。

中序遍历中A的下一个结点一定不在A的左子树里,所以在A的右子树里找。
若A只有一个右孩子,那A的下一个结点就是它。
若A的右孩子B有左孩子,那A的下一个结点就是B的最左边的孩子。

即在A的右子树里找最左边的结点。

还有一种情况是A没有孩子,基于此也有两种情况:
若A是其父节点的左孩子,那A的下一个结点就是其父结点;
若A是其父节点的右孩子,找A父亲的父结点的…的父结点C,直到C是C的父结点的左孩子。若找不到这样的C,那说明A是尾结点(中序遍历最后一个位置)

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
32
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 not None: #A有右孩子
pNode = pNode.right
if pNode.left is None:#A的右孩子没有左孩子
return pNode
else: #A的右孩子有左孩子,找到最左边的节点
while pNode.left is not None: #这里可以简化下把if去了,只用while
pNode = pNode.left
return pNode
else: #A没有右孩子,下一个节点在其父亲里
if pNode.next is not None:
temp = pNode
pNode = pNode.next
if pNode.left == temp: #A是其父亲的左节点,下一个节点就是其父亲
return pNode
#A是其父亲的右节点,下一个节点在A的父亲们里
while pNode.next is not None:
temp = pNode
pNode = pNode.next
if pNode.left == temp:
return pNode

#A是尾节点
return None
if help:小手一抖点个广告 or 大手一挥资助一下