Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9e6c23d

Browse files
add
1 parenta052ce1 commit9e6c23d

File tree

3 files changed

+137
-43
lines changed

3 files changed

+137
-43
lines changed

‎.idea/workspace.xml

Lines changed: 41 additions & 43 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎Target Offer/二叉树的下一个结点.py

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,4 +26,33 @@ def GetNext(self, pNode):
2626
pCurrent=pParent
2727
pParent=pCurrent.next
2828
pNext=pParent
29+
returnpNext
30+
31+
classSolution2:
32+
defGetNext(self,pNode):
33+
# 输入是一个空节点
34+
ifpNode==None:
35+
returnNone
36+
# 注意当前节点是根节点的情况。所以在最开始设定pNext = None, 如果下列情况都不满足, 说明当前结点为根节点, 直接输出None
37+
pNext=None
38+
# 如果输入节点有右子树，则下一个结点是当前节点右子树中最左节点
39+
ifpNode.right:
40+
pNode=pNode.right
41+
whilepNode.left:
42+
pNode=pNode.left
43+
pNext=pNode
44+
else:
45+
# 如果当前节点有父节点且当前节点是父节点的左子节点, 下一个结点即为父节点
46+
ifpNode.nextandpNode.next.left==pNode:
47+
pNext=pNode.next
48+
# 如果当前节点有父节点且当前节点是父节点的右子节点, 那么向上遍历
49+
# 当遍历到当前节点为父节点的左子节点时, 输入节点的下一个结点为当前节点的父节点
50+
elifpNode.nextandpNode.next.right==pNode:
51+
pNode=pNode.next
52+
whilepNode.nextandpNode.next.right==pNode:
53+
pNode=pNode.next
54+
# 遍历终止时当前节点有父节点, 说明当前节点是父节点的左子节点, 输入节点的下一个结点为当前节点的父节点
55+
# 反之终止时当前节点没有父节点, 说明当前节点在位于根节点的右子树, 没有下一个结点
56+
ifpNode.next:
57+
pNext=pNode.next
2958
returnpNext

‎Target Offer/对称的二叉树.py

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,4 +20,71 @@ def selfIsSymmetrical(self, pRoot1, pRoot2):
2020
ifpRoot1.val!=pRoot2.val:
2121
returnFalse
2222
returnself.selfIsSymmetrical(pRoot1.left,pRoot2.right)andself.selfIsSymmetrical(pRoot1.right,pRoot2.left)
23+
# 非递归实现判断二叉树是否对称
24+
# 利用前序遍历
25+
classSolution2:
26+
defisSymmetrical(self,pRoot):
27+
preList=self.preOrder(pRoot)
28+
mirrorList=self.mirrorPreOrder(pRoot)
29+
ifpreList==mirrorList:
30+
returnTrue
31+
returnFalse
32+
33+
defpreOrder(self,pRoot):
34+
ifpRoot==None:
35+
return [None]
36+
treeStack= []
37+
output= []
38+
pNode=pRoot
39+
whilepNodeorlen(treeStack)>0:
40+
whilepNode:
41+
treeStack.append(pNode)
42+
output.append(pNode.val)
43+
pNode=pNode.left
44+
ifnotpNode:
45+
output.append(None)
46+
iflen(treeStack):
47+
pNode=treeStack.pop()
48+
pNode=pNode.right
49+
ifnotpNode:
50+
output.append(None)
51+
returnoutput
52+
53+
defmirrorPreOrder(self,pRoot):
54+
ifpRoot==None:
55+
return [None]
56+
treeStack= []
57+
output= []
58+
pNode=pRoot
59+
whilepNodeorlen(treeStack)>0:
60+
whilepNode:
61+
treeStack.append(pNode)
62+
output.append(pNode.val)
63+
pNode=pNode.right
64+
ifnotpNode:
65+
output.append(None)
66+
iflen(treeStack):
67+
pNode=treeStack.pop()
68+
pNode=pNode.left
69+
ifnotpNode:
70+
output.append(None)
71+
returnoutput
72+
73+
pNode1=TreeNode(8)
74+
pNode2=TreeNode(6)
75+
pNode3=TreeNode(10)
76+
pNode4=TreeNode(5)
77+
pNode5=TreeNode(7)
78+
pNode6=TreeNode(9)
79+
pNode7=TreeNode(11)
80+
81+
pNode1.left=pNode2
82+
pNode1.right=pNode3
83+
pNode2.left=pNode4
84+
pNode2.right=pNode5
85+
pNode3.left=pNode6
86+
pNode3.right=pNode7
2387

88+
S=Solution2()
89+
result=S.isSymmetrical(pNode1)
90+
print(result)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp