leetcode笔记｜第五周 树专题

二叉树相关基础知识 https://blog.csdn.net/xiaoquantouer/article/details/65631708 leetcode二叉树相关教程 https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/59slxe/ https://leetcode-cn.com/leetbook/detail/data-structure-binary-tree/

剑指offer 27 二叉树的镜像

python可以平行赋值，就很方便。当tree为空的时候，return /。return。None / return root 都可以。时间复杂度：需要遍历所有节点O(N)，空间复杂度：二叉树O(log(n)，退化成链表O(n)。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def mirrorTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if not root: return # 为空的情况 return None return root 都对 root.right, root.left = self.mirrorTree(root.left), self.mirrorTree(root.right) return root

108 将升序数组转换为高度平衡二叉搜索树

BST的中序遍历为递增序列，所以可以最简单的，这个升序数组的中间为root，小的在左分支，大的在右分支。返回node，得到的就是整个BST。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ if not len(nums): return # 考虑为空 mid = (len(nums)) // 2 node = TreeNode(nums[mid]) left = nums[:mid] right = nums[mid+1:] node.left, node.right = self.sortedArrayToBST(left), self.sortedArrayToBST(right) return node

979 在二叉树中分配硬币

深度优先搜索，每一个node的当前金币数与1的差距就是过载量，也就是要走或者来的数量。叶子结点的和为返回的次数，每个叶子结点的过载量计算公式为 .val+L+R-1。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def distributeCoins(self, root): """ :type root: TreeNode :rtype: int """ self.ans = 0 def dfs(node): if not node: return 0 # not node时 没有.left .right 没有这句话下面会报错 L, R = dfs(node.left), dfs(node.right) self.ans += abs(L) + abs(R) return node.val + L + R - 1 dfs(root) return self.ans

1457 二叉树中的伪回文路径

二叉树的每一条路径，如果是可以组成回文串，就称为伪回文路径。计算root的伪回文路径数目。想法就是拿出每条路径（直到叶子结点），判断是否回文。拿出路径，使用list实现，每个不是叶子结点的node.val加入到path这个list中；判断是否叶子结点就是判断是否左右子结点都为None。判断是否回文，由于乱序，因此判断是否奇数个的字母只有一个即可。奇数可用&1 位计算实现。

from collections import Counter class Solution(object): def pseudoPalindromicPaths (self, root): def huiwen(path): coun = Counter(path) odd_num = 0 for i in coun: if coun[i] & 1: odd_num += 1 if odd_num == 2: return False return True if not root: return self.ans = 0 stack = [([root.val],root)] while stack: path, node = stack.pop() if not node.left and not node.right: if huiwen(path): self.ans += 1 if node.left: stack.append((path+[node.left.val], node.left)) if node.right: stack.append((path+[node.right.val], node.right)) return self.ans

1130 叶值的最小代价生成树

正整数数组，相邻两个叶子结点的父节点是两者的乘积，叶子结点顺序就按照数组的顺序排列，最终希望得到的非子节点的和越来越小。如此，比如四个，1234，可以12的到父节点，34得到父节点，然后两个父节点乘积得到根，求三个生成的非子节点的和最小。如果要求最小，其实有trick，就是让最小值在最底层，多次相乘求和这样比大的在最底层多次相乘求和要小得多。所以1，2，34，先34相乘求父节点，与2相乘求父节点，在于1相乘，1是最大的人，乘最多次的3/4最小，那么多个父节点的和是最小的。因此，可以循环遍历两个相邻的乘积最小的，丢掉较小的那一个，留下较大的那一个后面计算父节点要用，因为是每支树max的元素的乘积。ps，计算完相乘结果后加入入res中，求和。

class Solution: def mctFromLeafValues(self, arr: List[int]) -> int: res = 0 while len(arr)>=2: n = len(arr) select= 0 min_mul = arr[0] * arr[1] for i in range(1, n-1): if arr[i] * arr[i+1] < min_mul: min_mul = arr[i] * arr[i+1] select = i if arr[select] < arr[select+1]: del arr[select] else: del arr[select+1] res += min_mul return res

124 二叉树中的最大路径和

就是找一个二叉树的路径，和最大。路径6和就是当前节点+左子树+右子树，如果两个子树小于0那就不要了。

class Solution: def maxPathSum(self, root: TreeNode) -> int: self.ans = float('-inf') def dfs(root): if not root: return 0 right = dfs(root.right) left = dfs(root.left) self.ans = max(self.ans, left+right+root.val) return max(0, max(left, right)+root.val) dfs(root) return self.ans

968 监控二叉树

套路：遍历树，从下往上，当子节点xxx的时候，父节点应该是xxx的，同时设置一个变量self.res循环地更新。最终的节点状态是xxx的时候，会怎么影响self.res。这里每个节点可能：子节点需要相机，这个节点放一个相机；子节点放了相机，这个节点不需要相机；子节点被相机拍了，这个节点需要相机。注意临界条件，叶子结点的左右子节点可以看作被拍了；根节点需要相机的时候，最终数目+1。

class Solution(object): def minCameraCover(self, root): self.res = 0 def judge(node): if not node: return 0 # 无子节点可认为子节点被拍了 left = judge(node.left) right = judge(node.right) if not left and not right: return 1 # need camera if left == 1 or right == 1: self.res += 1 return 2 # put a camera if left == 2 or right == 2: return 0 # dont need a camera if judge(root) == 1: # 最终need camera要加一个哦 self.res += 1 return self.res