1、二叉树的遍历
1）递归实现遍历
def threeOrders(self , root ):
# write code here
def preorder(root):
if not root:
return []
return [root.val]+preorder(root.left)+preorder(root.right)
def inorder(root):
if not root:
return []
return inorder(root.left)+[root.val]+inorder(root.right)
def postorder(root):
if not root:
return []
return postorder(root.left)+postorder(root.right)+[root.val]
res=[]
res.append(preorder(root))
res.append(inorder(root))
res.append(postorder(root))
return res
2）迭代实现遍历
def threeOrders(self , root ):
# write code here
def preorder(root):
res = []
stack = []
cur = root
# 前序，模板：先用指针找到每颗子树的最左下角，然后进行进出栈操作
whilestack or cur:
whilecur:
stack.append(cur)
res.append(cur.val)
cur = cur.left
cur = stack.pop()
cur = cur.right
returnres
def inorder(root):
res = []
stack = []
cur = root
# 中序，模板：先用指针找到每颗子树的最左下角，然后进行进出栈操作
whilestack or cur:
whilecur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
returnres
def postorder(root):
res = []
stack = []
cur = root
# 中序，模板：先用指针找到每颗子树的最左下角，然后进行进出栈操作
whilestack or cur:
whilecur:
stack.append(cur)
res.append(cur.val)
cur = cur.right
cur = stack.pop()
cur = cur.left
returnres[::-1]
res=[]
res.append(preorder(root))
res.append(inorder(root))
res.append(postorder(root))
returnres
https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=191&&tqId=36147&rp=1&ru=/activity/oj&qru=/ta/job-code-high-algorithm/question-ranking
2、二叉树的右视图
1）迭代
2）递归
def rightsideview(root,level,path):
ifnot root:
return
iflevel>len(path):
path.append(root.val)
rightsideview(root.right,level+1,path)
rightsideview(root.left,level+1,path)
#root=recreate(xianxu , zhongxu)
res=[]
rightsideview(root,1,res)
returnres
https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0?tpId=117&&tqId=37848&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
3、根节点到叶子结点指定和值
1）是否存在
if not root:
return False
if root.val==sum and not root.left and not root.right:
return True
return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=117&&tqId=37719&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
2）打印路径
ret = list()
path = list()
def dfs(root, target):
if not root:
return
path.append(root.val)
target -= root.val
if not root.left and not root.right and target == 0:
ret.append(path[:])
dfs(root.left, target)
dfs(root.right, target)
path.pop()
#pop利用了栈的性质，注意的是：先进后出
dfs(root, sum)
return ret
https://www.nowcoder.com/practice/840dd2dc4fbd4b2199cd48f2dadf930a?tpId=117&&tqId=37718&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
4、路径和
1）根结点到叶子节点的所有路径和
if not root:
return 0
def preorder(root,sum1):
if not root:
return 0
sum1=10*sum1+root.val
if not root.left and not root.right:
return sum1
return preorder(root.left,sum1)+preorder(root.right,sum1)
return preorder(root,0)
https://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83?tpId=191&&tqId=36660&rp=1&ru=/activity/oj&qru=/ta/job-code-high-algorithm/question-ranking
2）最大路径和
self.res=float('-inf')
def pathmax(root):
if not root:
return 0
leftmax=max(0,pathmax(root.left))
rightmax=max(0,pathmax(root.right))
self.res=max(self.res,leftmax+rightmax+root.val)
return max(leftmax,rightmax)+root.val
if not root:
return 0
pathmax(root)
return self.res
https://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a?tpId=191&&tqId=36295&rp=1&ru=/activity/oj&qru=/ta/job-code-high-algorithm/question-ranking
