题目分析
有关树的题目,小伙伴们就要想到递归,这个要深深的印在脑海里面。本题和Leetcode 剑指Offer68-Ⅰ是姐妹类型,这个题目难度稍微大一些,上一题我没有拿出来讲解是因为过于简单。在二叉搜索树中查找,因为是搜索树,我们可以根据节点的大小选择固定的路,不用进行回溯,所以通过迭代即可,不用递归进行查找,**时间复杂度为$O(log(n))$。这个题目我们不知道树中节点的大小关系,因此需要进行递归查找,时间复杂度为$O(n)$**。
递归
在这里先给出我的笨方法,虽然时间复杂度和空间复杂度并不高,但是代码长度大,不美观。
我的思路是自底向上进行查找,当找到p或者q时,数量加1,当数量等于2时,说明该节点是最近的公共祖先。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
优化递归
要找两个节点的最近公共祖先,现在有三种情况,一个是两个节点都在某个节点的左孩子中,第二个是两个节点都存在于某个节点的右孩子中,第三个是两个节点一左一右分别存在于左孩子和右孩子中。
我们自底向上进行查找,当找到p或者q时返回p和q,p和q一定在某个节点的左右子树上,一个在左,一个在右,如果没有找到该节点,那么左右子树一定有一个是NULL,如果left = NULL,则return right,如果right = NULL,则return left,如果左右都不是NULL,说明找到了最近的公共祖先,返回root即可。
这个思路是比较难想的,代码却非常简单,也非常漂亮。算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
刷题总结
这个题目作为简单题,我不能接受,我想了很久,用了一种很笨的方法,虽然也是自底向上,但是代码不优美,这里提醒小伙伴们在刷题的时候,不能提交没有问题就进行下一题,一定要看一看别人的思路和方法,多多学习,这样才可以更好的提升自己。