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)