题目

235. 二叉搜索树的最近公共祖先【简单】

题解

两次遍历

1. 利用二叉搜索树的性质找到p、q结点，同时记录对应路径path_p和path_q
   （1）如果当前节点值>p值：转向左子树
   （2）如果当前节点值<p值：转向右子树
2. 遍历path_p和path_q，找到最大的 i ，使得path_p[i]==path_q[i]

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {List<TreeNode>path_p=findPath(root,p);List<TreeNode>path_q=findPath(root,q);TreeNode ansester=null;//祖先//找公共祖先for(int i=0;i<path_p.size()&&i<path_q.size();i++){if(path_p.get(i)==path_q.get(i))ansester=path_p.get(i);elsebreak;}return ansester;}//返回到节点p的路径public List<TreeNode> findPath(TreeNode root,TreeNode p){List<TreeNode>path=new ArrayList<>();while(root!=null){path.add(root);if(root==p)return path;else if(root.val>p.val)root=root.left;elseroot=root.right;}return path;}
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

一次遍历

从根节点开始遍历一次，

1. 如果当前节点值>p&q值：转向左子树
2. 如果当前节点值<p&q值：转向右子树
3. 不满足以上两条，则有两种情况
   （1）p、q分别在当前节点的左右子树中
   （2）当前节点就是p或q
   不管是以上哪种情况，都代表当前节点即为p、q的最近公共祖先

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(root!=null){//当前节点值>p&q值if(root.val>p.val&&root.val>q.val)root=root.left;//当前节点值<p&q值else if(root.val<p.val&&root.val<q.val)root=root.right;//找打最近公共祖先elsebreak;}return root;}
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$