题解 | #二叉搜索树的最近公共祖先#
二叉搜索树的最近公共祖先
https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f
// 直接层序遍历找到第一个介于p和q之间的节点
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param p int整型
* @param q int整型
* @return int整型
*/
public int lowestCommonAncestor (TreeNode root, int p, int q) {
// write code here
//
LinkedList<TreeNode> list = new LinkedList();
list.add(root);
if(p>q){
int t = q;
q = p;
p = t;
}
while(list.size()!=0){
TreeNode cur = list.removeFirst();
if(cur.val<=q && cur.val>=p){
return cur.val;
}
if(cur.left!=null){
list.addLast(cur.left);
}
if(cur.right!=null){
list.addLast(cur.right);
}
}
return -1;
}
}