自己做的网站项目面试,瑞昌市环保局网站建设,武威网站制作公司电话多少,网站运营建设250.统计同值子树 使用dfs深度搜索#xff0c;同值子树#xff0c;要满足三个条件#xff1a;
对于当前节点node#xff0c;他的左子树血脉纯净#xff08;为同值子树#xff09;#xff0c;右子树血脉纯净#xff08;为同值子树#xff09;#xff0c;node的值等于… 250.统计同值子树 使用dfs深度搜索同值子树要满足三个条件
对于当前节点node他的左子树血脉纯净为同值子树右子树血脉纯净为同值子树node的值等于左右子树节点的值。
全是if判断推理
class Solution:def countUnivalSubtrees(self, root: Optional[TreeNode]) - int:n, b self.dfs(root)return ndef dfs(self, root):if not root: return 0, Truen 0b Truen1, b1 self.dfs(root.left)n2, b2 self.dfs(root.right)n n1 n2if not b1 or not b2:b Falseif root.left and root.left.val ! root.val:b Falseif root.right and root.right.val ! root.val:b Falseif b: n 1return n, b 1120.子树的最大平均值 使用dfs 返回以root为根的所以节点的总和节点数量。
没有任何技巧全是感情
class Solution:def __init__(self):self.m 0def maximumAverageSubtree(self, root: Optional[TreeNode]) - float:self.dfs(root)return self.mdef dfs(self, root):# 返回以root为根的所以节点的总和节点数量if not root: return 0, 0s1, c1 self.dfs(root.left)s2, c2 self.dfs(root.right)s s1 s2 root.valc c1 c2 1self.m max(self.m, s/c)return s, c545.二叉树的边界 可以把题目分成三个问题使用三个dfs解决可以发现左边界和右边界很相似dfs传入一个idx判断是先从左走还是先从右走另外题目说根节点 不是 叶节点。但是数据中存在只有一个节点的情况需要注意。
class Solution:def __init__(self):self.leaf []def boundaryOfBinaryTree(self, root: Optional[TreeNode]) - List[int]:if not root.left and not root.right: return [root.val]ans []if root.left:l self.find_ls(root, 0)ans lelse:ans [root.val]self.find_leaf(root)ans self.leafif root.right:r self.find_ls(root, 1)ans r[::-1]ans.pop()return ansdef find_ls(self, root, idx):ans [root.val]if idx 1:root.left, root.right root.right, root.leftif root.left:ans self.find_ls(root.left, idx)elif root.right:ans self.find_ls(root.right, idx)else:return []return ansdef find_leaf(self, root):if root.left:self.find_leaf(root.left)if root.right:self.find_leaf(root.right)if not root.left and not root.right:self.leaf.append(root.val) 366.寻找二叉树的叶子节点 任然使用dfs深度搜索记录每一层的位置然后在ans相应位置中插入
class Solution:def __init__(self):self.length 0self.ans []def findLeaves(self, root: Optional[TreeNode]) - List[List[int]]:self.dfs(root)return self.ansdef dfs(self, root):if not root: return 0n1 self.dfs(root.left)n2 self.dfs(root.right)n max(n1, n2)if self.length - 1 n:self.length 1self.ans.append([])self.ans[n].append(root.val)return n 1
还能补充知识吗我的大脑
