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)