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

Commitaccc4fc

Browse files
add 4 leetcodes
1 parentd1f5468 commitaccc4fc

6 files changed

+249
-114
lines changed

‎.idea/workspace.xml

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

‎Target Offer/把二叉树打印成多行.py

Lines changed: 4 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -10,11 +10,10 @@ def __init__(self, x):
1010
self.right=None
1111
classSolution:
1212
# 返回二维列表[[1,2],[4,5]]
13-
defPrint(self,pRoot):
13+
deflevelOrder(self,pRoot):
1414
ifpRoot==None:
1515
return []
16-
nodes= [pRoot]
17-
result= []
16+
nodes,res= [pRoot], []
1817
whilenodes:
1918
curStack,nextStack= [], []
2019
fornodeinnodes:
@@ -23,9 +22,9 @@ def Print(self, pRoot):
2322
nextStack.append(node.left)
2423
ifnode.right:
2524
nextStack.append(node.right)
26-
result.append(curStack)
25+
res.append(curStack)
2726
nodes=nextStack
28-
returnresult
27+
returnres
2928

3029

3130
pNode1=TreeNode(8)

‎leetcode/101. Symmetric Tree.py

Lines changed: 19 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -25,10 +25,11 @@ def __init__(self, x):
2525
classSolution(object):
2626
# recursive
2727
defisSymmetric(self,root):
28-
returnself.selfIsSymmetrical(root,root)
29-
defselfIsSymmetrical(self,pRoot1,pRoot2):
28+
returnself._Symmetrical(root,root)
29+
def_Symmetrical(self,pRoot1,pRoot2):
3030
ifpRoot1andpRoot2:
31-
returnpRoot1.val==pRoot2.valandself.selfIsSymmetrical(pRoot1.left,pRoot2.right)andself.selfIsSymmetrical(pRoot1.right,pRoot2.left)
31+
returnpRoot1.val==pRoot2.valandself._Symmetrical(pRoot1.left,pRoot2.right)andself._Symmetrical(
32+
pRoot1.right,pRoot2.left)
3233
else:
3334
returnpRoot1==pRoot2
3435

@@ -43,6 +44,21 @@ def isSymmetric2(self, root):
4344
else:
4445
now= [jforiinnowififorjin (i.left,i.right)]
4546
returnTrue
47+
# modify iterative(BFS)
48+
defisSymmetric_2(self,root):
49+
ifroot:
50+
nodeStack= [root]
51+
whilenodeStack:
52+
vals= [node.valifnodeelseNonefornodeinnodeStack]
53+
iflist(reversed(vals))!=vals:
54+
returnFalse
55+
else:
56+
preStack= [nodefornodeinnodeStackifnode]
57+
nodeStack= []
58+
forpreNodeinpreStack:
59+
nodeStack.append(preNode.left)
60+
nodeStack.append(preNode.right)
61+
returnTrue
4662

4763
# iterative(DFS)
4864
defisSymmetric3(self,root):
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
'''
2+
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
3+
4+
For example:
5+
Given binary tree [3,9,20,null,null,15,7],
6+
3
7+
/\
8+
9 20
9+
/\
10+
15 7
11+
return its level order traversal as:
12+
[
13+
[3],
14+
[9,20],
15+
[15,7]
16+
]
17+
'''
18+
# Definition for a binary tree node.
19+
classTreeNode(object):
20+
def__init__(self,x):
21+
self.val=x
22+
self.left=None
23+
self.right=None
24+
25+
classSolution(object):
26+
deflevelOrder(self,root):
27+
ifnotroot:
28+
return []
29+
res,level= [], [root]
30+
whilelevel:
31+
res.append([node.valfornodeinlevel])
32+
temp= []
33+
fornodeinlevel:
34+
temp.extend([node.left,node.right])
35+
level= [nodefornodeintempifnode]
36+
returnres
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
'''
2+
Given preorder and inorder traversal of a tree, construct the binary tree.
3+
'''
4+
classTreeNode(object):
5+
def__init__(self,x):
6+
self.val=x
7+
self.left=None
8+
self.right=None
9+
10+
classSolution(object):
11+
# recursion
12+
defbuildTree(self,preorder,inorder):
13+
ifnotpreorderornotinorder:
14+
return
15+
root=TreeNode(preorder[0])
16+
ind=inorder.index(preorder.pop(0))
17+
root.left=self.buildTree(preorder,inorder[0:ind])
18+
root.right=self.buildTree(preorder,inorder[ind+1:])
19+
returnroot
20+
# method2, faster!!
21+
defbuildTree2(self,preorder,inorder):
22+
self.Ind=0
23+
ind= {val:indforind,valinenumerate(inorder)}
24+
head=self.build(0,len(preorder)-1,preorder,inorder,ind)
25+
returnhead
26+
27+
defbuild(self,start,end,preorder,inorder,ind):
28+
ifstart<=end:
29+
mid=ind[preorder[self.Ind]]
30+
self.Ind+=1
31+
root=TreeNode(inorder[mid])
32+
root.left=self.build(start,mid-1,preorder,inorder,ind)
33+
root.right=self.build(mid+1,end,preorder,inorder,ind)
34+
returnroot
35+
# Interative
36+
defbuildTreeInter(self,preorder,inorder):
37+
iflen(preorder)==0:
38+
returnNone
39+
40+
head=TreeNode(preorder[0])
41+
stack= [head]
42+
preInd,inInd=1,0
43+
44+
whilepreInd<len(preorder):
45+
temp=None
46+
node=TreeNode(preorder[preInd])
47+
whilestackandstack[-1].val==inorder[inInd]:
48+
temp=stack.pop()
49+
inInd+=1
50+
iftemp:
51+
temp.right=node
52+
else:
53+
stack[-1].left=node
54+
stack.append(node)
55+
preInd+=1
56+
57+
returnhead
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
'''
2+
Given inorder and postorder traversal of a tree, construct the binary tree.
3+
'''
4+
5+
# Definition for a binary tree node.
6+
classTreeNode(object):
7+
def__init__(self,x):
8+
self.val=x
9+
self.left=None
10+
self.right=None
11+
12+
classSolution(object):
13+
defbuildTree(self,inorder,postorder):
14+
ifnotinorderornotpostorder:
15+
returnNone
16+
17+
root=TreeNode(postorder.pop())
18+
ind=inorder.index(root.val)
19+
20+
root.right=self.buildTree(inorder[ind+1:],postorder)
21+
root.left=self.buildTree(inorder[:ind],postorder)
22+
returnroot
23+
24+
# method2, faster!!
25+
defbuildTree2(self,inorder,postorder):
26+
self.postInd=len(postorder)-1
27+
ind= {val:indforind,valinenumerate(inorder)}
28+
head=self.build(0,len(postorder)-1,inorder,postorder,ind)
29+
returnhead
30+
31+
defbuild(self,start,end,inorder,postorder,ind):
32+
ifstart<=end:
33+
mid=ind[postorder[self.postInd]]
34+
self.postInd-=1
35+
root=TreeNode(inorder[mid])
36+
root.right=self.build(mid+1,end,inorder,postorder,ind)
37+
root.left=self.build(start,mid-1,inorder,postorder,ind)
38+
returnroot
39+
40+
s=Solution()
41+
print(s.buildTree2([1,2,3,4],[2,4,3,1]))

0 commit comments

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