我发现只要是带了二叉搜索树的,都需要使用它的特性:
左节点比根节点小
右节点比根节点大
首先判断p、q是否有其中一个在根节点上:
这样就会造成本身就是最近公共祖先
判断根节点下是否有p,q子节点,可以使用p<root.val&&q>root.val,不过在这里有一个坑,题目并没有指定p一定是左节点、q一定是右节点,所以一定要多加一个q<root.val&&p>root.val,这样就会避免。
什么情况p,q在左节点呢:
p、q都小于root.val时
什么情况p,q在右节点呢:
p,q大于root。val时
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return ans;
}
TreeNode ans = null;
boolean f = true;
private void dfs(TreeNode root, TreeNode p, TreeNode q) {
if (f) {
if (root == null) {
return;
} else if (root.val == p.val || root.val == q.val) {
ans = root;
f = false;
}
if (root.val > p.val && q.val > root.val || root.val < p.val && q.val < root.val) {
ans = root;
f = false;
} else if (root.val > p.val && root.val > q.val) {
dfs(root.left, p, q);
} else if (root.val < p.val && root.val < q.val) {
dfs(root.right, p, q);
}
}
}
然后就是插入二叉搜索树元素,这里我用迭代倒是做出来了,使用递归时,对递归理解还是不够,没写出来,看了题解:
插入二叉搜索树的元素要遵循:
左节点比根节点小
右节点比根节点大
所以进行迭代的条件就是判断待插入元素在左右节点的方向。
package shuJuJieGouYuSuanFa.erChaShu;
public class likou701 {
public static void main(String[] args) {
TreeNode root = TreeNode.getBST();
print(new likou701().dfs(root, 14));
}
//递归
private TreeNode dfs(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (root.val > val) {
root.left = dfs(root.left, val);
} else {
root.right = dfs(root.right, val);
}
return root;
}
private static void print(TreeNode r) {
if (r == null) {
return;
}
System.out.print(r.val + " ");
print(r.left);
print(r.right);
}
//迭代
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return root = new TreeNode(val);
}
TreeNode t = root;
TreeNode p = t;
while (t != null) {
p = t;
if (t.val < val) {
t = t.right;
if (t == null) {
p.right = new TreeNode(val);
}
} else {
t = t.left;
if (t == null) {
p.left = new TreeNode(val);
}
}
}
return root;
}
}