给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
1 | 3 |
示例 1:
1 | 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 |
示例 2:
1 | 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 |
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
方法一:递归
1 | /** |
复杂度分析:时间复杂度和空间复杂度均为O(n)。其中,n为二叉树中结点的个数。
方法二:递归求路径
首先,按照先序遍历的顺序,分别寻找从根结点到结点p和q的路径;
然后,求这两条路径的最后一个公共结点,即为p和q的最近公共祖先。
1 | /** |
复杂度分析:时间复杂度和空间复杂度均为O(n)。其中,n为二叉树中结点的个数。
方法三:迭代求路径
1 | /** |
复杂度分析:时间复杂度和空间复杂度均为O(n)。其中,n为二叉树中结点的个数。