仅为个人记录复盘学习历程，解题思路来自代码随想录

代码随想录刷题笔记总结网址:
代码随想录

二叉搜索树的最近公共祖先">235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

提供参数：根结点root

关键思路：二叉搜索树和普通二叉树的区别在于它的左右是有顺序的，故通过选择进行确定遍历左子树还是右子树，不需要进行回溯，在本题中体现为判断当前节点值是否在p，q节点值的区间内。出现最近公共祖先只有两种情况：

1.左子树出现p（q），右子树出现q（p）。这种情况下该结点就是最近公共祖先。

2.两个节点都在同一个子树，那么需要继续向该子树遍历。

在本题中，判断是否为最近公共祖先条件为是否满足当前节点值在区间[p,q]或[q,p]中。

情况1显然满足该条件。

情况二中显然也满足该条件，两个节点出现在同一个子树，继续遍历，在一条路径上的情况找公共祖先节点也可由是否满足区间来判断。

代码大致如下：

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {return traversal(root,p,q);}public TreeNode traversal(TreeNode node, TreeNode p, TreeNode q){//1.终止条件if(node==null)return null;//2.单层递归逻辑//2.1全在左子树if(node.val>p.val&&node.val>q.val){TreeNode left=traversal(node.left,p,q);if(left!=null)return left;}//2.2全在右子树if(node.val<p.val&&node.val<q.val){TreeNode right=traversal(node.right,p,q);if(right!=null)return right;}//2.3在中间节点return node;}

701.二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

提供参数：根结点root，值val。

关键思路：简单遍历二叉搜索树找到提供val构造出节点应该在的位置，并与它的父节点联系起来。

代码大致如下：

    public TreeNode insertIntoBST(TreeNode root, int val) {//1.终止条件if(root==null){TreeNode node=new TreeNode(val);return node;}//2.单层递归逻辑//2.1if(root.val>val)root.left=insertIntoBST(root.left,val);if(root.val<val)root.right=insertIntoBST(root.right,val);return root;}