二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点p、q,最近公共祖先表示为一个节点x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

提示:

  • 树中节点数目在范围[2, 10^5]内。
  • -10^9 <= Node.val <= 10^9
  • 所有Node.val互不相同。
  • p != q
  • p和q均存在于给定的二叉树中。

二叉树最大路径和

路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点,且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点root,返回其最大路径和。

提示:

  • 树中节点数目范围是$[1, 3 * 10^4]$
  • -1000 <= Node.val <= 1000
|