题解 | 二叉搜索树的最近公共祖先
二叉搜索树的最近公共祖先
https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f
import java.util.*;
public class Solution {
public boolean flag = false;
public int lowestCommonAncestor (TreeNode root, int p, int q) {
// write code here
ArrayList<Integer> listP = new ArrayList<>();
ArrayList<Integer> listQ = new ArrayList<>();
dfs(root,listP,p);
flag = false;
dfs(root,listQ,q);
int res = 0;
for(int i = 0;i<listP.size() && i<listQ.size();i++){
if(listP.get(i).equals(listQ.get(i))){
res = listP.get(i);
}else{
break;
}
}
return res;
}
public void dfs(TreeNode root, ArrayList<Integer> list, int num){
if(flag || root == null){
return ;
}
// 将根节点添加到路径
list.add(root.val);
// 当找到目标节点，将flag=true，表示无需进行回溯操作
if(root.val == num){
flag = true;
return;
}
// 遍历左右子树
dfs(root.left,list,num);
dfs(root.right,list,num);
if(flag) return;
list.remove(list.size() - 1);
}
}
海康威视公司福利 1382人发布