查找二叉树子节点的最近共同父节点
分析
实现
算法复杂度
其他算法
题目升级
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。...实例1
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。...实例2
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身...说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。...,二叉搜索树变成了一个类似于链表的结构,而p , q p,qp,q是在最底端的两个节点那么搜索p , q p,qp,q节点的时间复杂度都可以达到n nn(n nn为树中节点个数),时间复杂度为O ( n