二叉树的最近公共祖先

给定一个二叉树的根节点 root，以及树中的两个节点 p 和 q，找出该树中 p 和 q 的最近公共祖先（LCA）。

最近公共祖先的定义：对于树中的两个节点 p、q，最近公共祖先是指同时拥有 p 和 q 作为后代的最低节点（允许一个节点是它自己的后代）。

约定

• p 和 q 均存在于给定的二叉树中。
• p != q，且所有节点的值互不相同。
• 返回的是从该祖先节点出发的整棵子树（序列化为层序数组）。

输入

• root：二叉树根节点，用力扣层序数组表示，例如 [3,5,1,6,2,0,8,null,null,7,4]
• p：目标节点，用单元素层序数组表示其值，例如 [5]
• q：目标节点，用单元素层序数组表示其值，例如 [1]

输出

最近公共祖先节点对应的层序数组（从该节点开始序列化整棵子树）。

示例一

输入：

root = [3,5,1,6,2,0,8,null,null,7,4], p = [5], q = [1]

输出：

[3,5,1,6,2,0,8,null,null,7,4]

解释：节点 5 和节点 1 的最近公共祖先是节点 3。

示例二

输入：

root = [3,5,1,6,2,0,8,null,null,7,4], p = [5], q = [4]

输出：

[5,6,2,null,null,7,4]

解释：节点 5 和节点 4 的最近公共祖先是节点 5（因为根据定义，一个节点可以是它自己的后代）。

示例三

输入：

root = [1,2], p = [1], q = [2]

输出：

[1,2]

平台变体说明

在力扣原题中，p 和 q 是 root 树中的真实节点引用。本平台通过数组分别独立构建 root、p、q 三个对象，因此 p、q 与 root 树中的节点不是同一个对象引用。参考解据此改为按节点值匹配目标节点（题目保证树中所有值互不相同，因此值比较是确定且正确的）。