leetcode尊享面试——二叉树（python）

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, c

545.二叉树的边界

 可以把题目分成三个问题，使用三个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

还能补充知识吗！！！我的大脑🧠