思路:本题依旧可以使用昨天的二叉树求最近公共节点的方法，但是由于二叉搜索树本身有序的特性，可以大大简化问题，因为二叉搜索树是有序的，可以直接进行从上往下的遍历，判断节点大小在两个要求的值之间即可返回，也不需要遍历一颗完整的树
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) {
// root的值比p或者q都大 则递归遍历root的左子树
TreeNode left = lowestCommonAncestor(root.left,p,q);
if (left != null) return left;
}
// root的值比p或者q都小 则递归遍历root的右子树
if (root.val < p.val && root.val < q.val){
TreeNode right = lowestCommonAncestor(root.right,p,q);
if (right != null) return right;
}
return root;
}
}
思路:二叉搜索树的插入节点，是在原有树的基础上进行添加节点，本题关键在与查找合适的插入位置，用左右子树接收递归返回的节点。
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
// 找到空的插入点 建立新节点 完成插入
if (root == null){
TreeNode node = new TreeNode(val);
return node;
}
// 目标值太小 在左子树查找
if (root.val > val){
// 用root.left完成接收
root.left = insertIntoBST(root.left,val);
}
// 目标值太大 在右子树查找
if (root.val < val){
// 用root.right完成接收
root.right = insertIntoBST(root.right,val);
}
return root;
}
}
