Python算法练习 10.15

leetcode 2130 链表的最大孪生和

在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。

• 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和 定义为一个节点和它孪生节点两者值之和。

给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

示例 1：

输入：head = [5,4,2,1]
输出：6
解释：
节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
链表中没有其他孪生节点。
所以，链表的最大孪生和是 6 。

示例 2：

输入：head = [4,2,2,3]
输出：7
解释：
链表中的孪生节点为：
- 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
- 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。
所以，最大孪生和为 max(7, 4) = 7 。

先用快慢指针找到表中点，从中点开始用头插法，反转表的后半部分，最后从头开始遍历两个表，记录最大和即可。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def pairSum(self, head):""":type head: Optional[ListNode]:rtype: int"""head = ListNode(0, head)fast = slow = head.nextwhile fast != None:slow = slow.nextfast = fast.next.nextreverseHead = ListNode(0, None)slowPre = slowwhile slow != None:slowPre = slowPre.nextslow.next = reverseHead.nextreverseHead.next = slowslow = slowPrenode1 = head.nextnode2 = reverseHead.nextmaxVal = 0while node1 and node2:maxVal = max(node1.val + node2.val, maxVal)node1 = node1.nextnode2 = node2.nextreturn maxVal

 leetcode 104 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

 简单的前序遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""def goNextLevel(root, depth):depthLeft = depthRight = depthif root:depth += 1depthLeft = goNextLevel(root.left, depth)depthRight = goNextLevel(root.right, depth)return max(depthLeft, depthRight)depth = 0if not root:return 0else:maxdepth = goNextLevel(root, depth)return maxdepth

leetcode 872 叶子相似的树

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

 

示例 1：

输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true

示例 2：

输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false

 本质就还是前序遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def leafSimilar(self, root1, root2):""":type root1: TreeNode:type root2: TreeNode:rtype: bool"""def goNextLevel(root, LeafArr):if not root.left and not root.right:LeafArr.append(root.val)returnif root.left:goNextLevel(root.left, LeafArr)if root.right:goNextLevel(root.right, LeafArr)      root1LeafArr = []root2LeafArr = []if root1:goNextLevel(root1, root1LeafArr)if root2:goNextLevel(root2, root2LeafArr)return root1LeafArr == root2LeafArr

 leetcode 1448 统计二叉树中好节点的数目

给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。

 

示例 1：

输入：root = [3,1,4,3,null,1,5]
输出：4
解释：图中蓝色节点为好节点。
根节点 (3) 永远是个好节点。
节点 4 -> (3,4) 是路径中的最大值。
节点 5 -> (3,4,5) 是路径中的最大值。
节点 3 -> (3,1,3) 是路径中的最大值。

示例 2：

输入：root = [3,3,null,4,2]
输出：3
解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。

 递归函数忘了写最后一句return，导致goodNum总是None

还是前序遍历，没什么好说的

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def goodNodes(self, root):""":type root: TreeNode:rtype: int"""# 记录从根节点遍历到该叶子节点的最大值，如果这个最大值不大于叶子节点的值，就是好节点def goNextLevel(root, goodNum, maxVal):if maxVal <= root.val:goodNum += 1if not root.left and not root.right:return goodNummaxVal = max(maxVal, root.val) if root.left:goodNum = goNextLevel(root.left, goodNum, maxVal)if root.right:goodNum = goNextLevel(root.right, goodNum, maxVal)return goodNumgoodNum = 0maxVal = root.valif not root:return goodNumelse:return goNextLevel(root, goodNum, maxVal)