记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
2/12 145. 二叉树的后序遍历
后序遍历：左右根
取值时根右左，结果倒序
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def postorderTraversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ret =[]
stack=[]
if not root:
return ret
stack.append(root)
while stack:
v = stack.pop()
if v.left:
stack.append(v.left)
if v.right:
stack.append(v.right)
ret.append(v.val)
ret.reverse()
return ret
2/13 987. 二叉树的垂序遍历
dfs 记录每一个col下的(row,v)
对col从小到大考虑 每一个col的list tmp
在tmp中根据row,v排序 得到需要的v序列
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def verticalTraversal(root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
from collections import defaultdict
global dic
dic = defaultdict(list)
def find(node,row,col):
global dic
if not node:
return
dic[col].append((row,node.val))
find(node.left,row+1,col-1)
find(node.right,row+1,col+1)
find(root,0,0)
l = dic.keys()
l.sort()
ans = []
for i in l:
tmp = dic[i]
tmp.sort(key=lambda x:(x[0],x[1]))
t = [x[1] for x in tmp]
ans.append(t)
return ans
2/14 102. 二叉树的层序遍历
BFS 广搜遍历
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def levelOrder(root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
ret =[]
if root==None:
return ret
nodelist = [(root,0)]
while len(nodelist)>0:
node,level = nodelist[0]
if level <= len(ret)-1:
res = ret[level]
res.append(node.val)
ret[level] = res
else:
res = [node.val]
ret.append(res)
nodelist.pop(0)
if node.left:
nodelist.append((node.left,level+1))
if node.right:
nodelist.append((node.right,level+1))
return ret
2/15 107. 二叉树的层序遍历 II
BFS 记录层数
将最深的层放在前面
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def levelOrderBottom(root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
l =[]
l.append((root,0))
tmpl=[]
tmp=0
ret=[]
while len(l)>0:
v,level = l.pop(0)
if tmp==level:
tmpl.append(v.val)
else:
ret=[tmpl]+ret
tmpl=[v.val]
tmp=level
if v.left:
l.append((v.left,level+1))
if v.right:
l.append((v.right,level+1))
ret =[tmpl]+ret
return ret
2/16 103. 二叉树的锯齿形层序遍历
记录层数 偶数层正序 奇数层逆序
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def zigzagLevelOrder(root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
l =[]
l.append((root,0))
tmpl=[]
tmp=0
ret=[]
while len(l)>0:
v,level = l.pop(0)
if tmp==level:
tmpl.append(v.val)
else:
if level%2==0:
tmpl.reverse()
ret.append(tmpl)
tmpl=[v.val]
tmp=level
if v.left:
l.append((v.left,level+1))
if v.right:
l.append((v.right,level+1))
if level%2==1:
tmpl.reverse()
ret.append(tmpl)
return ret
2/17 429. N 叉树的层序遍历
BFS
class Node(object):
def __init__(self, val=None, children=None):
self.val = val
self.children = children
def levelOrder(root):
"""
:type root: Node
:rtype: List[List[int]]
"""
ans = []
if not root:
return ans
l = [root]
while l:
tmp = []
val = []
for node in l:
val.append(node.val)
tmp.extend(node.children)
ans.append(val)
l = tmp
return ans
2/18 589. N 叉树的前序遍历
1.递归
2.迭代 存入栈中每次取栈顶元素 并将子节点倒序压入栈中
class Node(object):
def __init__(self, val=None, children=None):
self.val = val
self.children = children
def preorder(root):
"""
:type root: Node
:rtype: List[int]
"""
ans = []
def dfs(node):
if not node:
return
ans.append(node.val)
for c in node.children:
dfs(c)
dfs(root)
return ans
def preorder2(root):
"""
:type root: Node
:rtype: List[int]
"""
stack = [root]
ans = []
while stack:
node = stack.pop()
if node :
ans.append(node.val)
for c in node.children[::-1]:
stack.append(c)
return ans
