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

0%

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

《剑指offer》python实现系列,全目录

一开始没懂题目什么意思。就是给二叉树的一个结点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:直接由这个结点推出中序遍历中下一个结点

1
2
3
4
			a
b c
d e d e
xx h i x x x x #x表示None

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

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

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

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

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
class TreeLinkNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.next = None
class Solution:
def GetNext(self, pNode):
# test
if pNode == None:
return None

if pNode.right:#如果有右子树
pNode = pNode.right
if pNode.left:#有左子树
while pNode.left: #一直向左找左叶子结点
pNode = pNode.left
return pNode
else:
return pNode

elif pNode.next:#没有右孩子,有父节点,节点是h或i的情况
while pNode.next:
temp =pNode
pNode = pNode.next
if pNode.left == temp:
return pNode
return None #找不到这样的节点,说明是右下角的叶子结点
else:#pNode是根结点
return None
if help:小手一抖点个广告 or 大手一挥资助一下