北京东宏建设网站,网页代理最干净最悠久,提供手机自适应网站,皇岗网站建设leetcode 2130 链表的最大孪生和
在一个大小为 n 且 n 为 偶数 的链表中#xff0c;对于 0 i (n / 2) - 1 的 i #xff0c;第 i 个节点#xff08;下标从 0 开始#xff09;的孪生节点为第 (n-1-i) 个节点 。
比方说#xff0c;n 4 那么节点 0 是节点 3 的孪…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, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def pairSum(self, head)::type head: Optional[ListNode]:rtype: inthead 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, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def maxDepth(self, root)::type root: TreeNode:rtype: intdef 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, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def leafSimilar(self, root1, root2)::type root1: TreeNode:type root2: TreeNode:rtype: booldef 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 root2LeafArrleetcode 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, val0, leftNone, rightNone):
# 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)
