又是好久都没有刷题今天把二叉树的题顺一遍236.二叉树的最近公共祖先给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”示例 1输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1输出3解释节点5和节点1的最近公共祖先是节点3思路递归函数的作用就是看左子树和右子树是否有 p,q有的话那当前节点就是p q节点的最近公共祖先直接返回否则的话左子树存在就返回左子树右子树存在就返回右子树。如果都不存在就返回None# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root or root p or root q: return root left self.lowestCommonAncestor(root.left,p,q) right self.lowestCommonAncestor(root.right,p,q) if left and right: return root if left: return left if right: return right return None124.二叉树的最大路径和二叉树中的路径被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点root返回其最大路径和。示例 1输入root [1,2,3]输出6解释最优路径是 2 - 1 - 3 路径和为 2 1 3 6示例 2输入root [-10,9,20,null,null,15,7]输出42解释最优路径是 15 - 20 - 7 路径和为 15 20 7 42 思路左面返回左面的最大值和右面返回右面的最大值和。在这个递归的过程中顺便更新一个最大和# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def maxPathSum(self, root: Optional[TreeNode]) - int: # 每个节点都要判断 max(左) max(右) 自己 0 的话不累积 # 全局变量小黑板保存当前最大的值 # 每次返回左面的直棍和右面直棍 if not root: return 0 # 这个全局变量应该写在递归的外部 # 在左子树和右子树返回最大的值的时候额外把全局变量更新一下 self.maxans float(-inf) self.sideMax(root) return self.maxans def sideMax(self,node): if not node: return 0 left self.sideMax(node.left) right self.sideMax(node.right) left max(0,left) right max(0,right) self.maxans max(self.maxans,node.val left right) return node.val max(left,right)