第十七天(树)
今天完成题目:1628,1584,965,669 1628:二叉树的最近祖先
一开始使用了层次遍历,较为麻烦,需要填满所有空缺的地方,超出了时间限制
而后改成深度遍历,AC
在递归中,可以使用p_list.copy()来浅拷贝一个数据
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: if not root or root == p or root == q: return root # 找到p或q left = self.lowestCommonAncestor(root.left, p, q) # pq谁先找到就返回谁 right = self.lowestCommonAncestor(root.right, p, q) #pq谁先找到就先返回谁 if not left: return right # 若pq都在右边,那么最先找到right的就是最近公共祖先 if not right: return left # 若pq都在左边,那么最先找到left的就是最近公共祖先 return root # 若pq在左右两边都有,那么root就是结果
1584:从上到下打印二叉树
利用队列的FIFO特性层序遍历二叉树
在每一层利用一个for循环实现一层的遍历,并临时存储下一层
队列可以是collections包的deque双向队列[pop()和popleft(),append()和appendleft()]
也可以是queue包的Queue[put()入队和get()出队].
1627:二叉搜索树的最近公共祖先
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 或p,q在同一侧,p,q某一个先遍历到,root.val==p.val or root.val==q.val
if not root or root == p or root == q: return root
if root.val>p.val and root.val>q.val: # p,q在左子树中
return self.lowestCommonAncestor(root.left,p,q)
elif root.val<p.val and root.val<q.val: # p,q在右子树中
return self.lowestCommonAncestor(root.right,p,q)
else: # p,q在左右子树中,root为结果
return root
965:单值二叉树
通过栈迭代遍历所有数值,只要有一个不同,返回false即可
669:修剪二叉树
先找出范围内的树
而后将这些数按顺序插入二叉搜索树中(不需要高度平衡)
最后更新于
这有帮助吗?