1. 力扣450：删除二叉搜索树的节点
1. 题目：
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
示例 1:
输入：root = [5,3,6,2,4,null,7], key = 3 输出：[5,4,6,2,null,null,7] 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0 输出: [5,3,6,2,4,null,7] 解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0 输出: []
提示:
- 节点数的范围
[0, 104]. -105 <= Node.val <= 105- 节点值唯一
root是合法的二叉搜索树-105 <= key <= 105
进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
2. 题解
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {TreeNode root1;public TreeNode deleteNode(TreeNode root, int key) {root1 = root;TreeNode p = root;TreeNode parent = null;while (p != null) {if (p.val > key) {parent = p;p = p.left;} else if (p.val < key) {parent = p;p = p.right;} else {break;}}if (p == null) {return root;}if (p.left == null && p.right == null) {shift(parent, p, null);} else if (p.left != null && p.right == null) {shift(parent, p, p.left);} else if (p.left == null && p.right != null) {shift(parent, p, p.right);} else {TreeNode s = p.right;TreeNode sParent = p;while (s.left != null) {sParent = s;s = s.left;}if (p != sParent) {shift(sParent, s, s.right);s.right = p.right;}shift(parent, p, s);s.left = p.left;}return root1;}public void shift(TreeNode parent, TreeNode deleted, TreeNode child) {if (parent == null) {root1 = child;} else if (parent.left == deleted) {parent.left = child;} else {parent.right = child;}}
}2. 力扣98 ：验证二叉搜索树
1. 题目：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左
子树
只包含 小于 当前节点的数。 - 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
- 树中节点数目范围在
[1, 104]内 -231 <= Node.val <= 231 - 1
2.思路（递归）：
对于该题我们可以使用递归的方法去解决。由于二叉搜索树的特性，一个节点比其左孩子的值要大，比右孩子的要小（如果其有左右孩子的话），但由此条件是不够推出其是二叉搜索树的。如果某节点的值满足比其左子树的最大值要大，比其右子树的最小值要小，并且其左孩子和右孩子都满足该规则的话，是可以推出该是一个有效的二叉搜索树的。
3. 题解：
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isValidBST(TreeNode root) {return doisValidBST(root);}public boolean doisValidBST(TreeNode node) {// 如果是空树，直接返回if(node == null) {return true;}boolean flag = true;TreeNode p = null;// 该节点存在左子树的前提下，满足节点比左子树所有节点的最大值要大if ((p = node.left) != null) {while(p.right != null) {p = p.right;}flag = p.val < node.val ? true : false;}// 如果flag为false，就不必要进行下列的判断了if(flag){//在节点存在右子树的前提下，满足节点比右子树的所有节点的最小值要小if ((p = node.right) != null) {while(p.left != null) {p = p.left;}flag = p.val > node.val ? true : false;}}if(node.left == null && node.right == null) {return flag;} else if (node.left != null && node.right == null) {return flag==true && isValidBST(node.left);} else if (node.left == null && node.right != null) {return flag && isValidBST(node.right);} else {return flag && isValidBST(node.left) && isValidBST(node.right);}}
}4. 思路（有序递增数列）
由题可知，中序遍历得到的序列一定是递增数列。
5. 题解：
class Solution {Deque<Integer> deque = new LinkedList<>();public boolean isValidBST(TreeNode root) {midTraverse(root);while (!deque.isEmpty()){int i1 = deque.pop();if(deque.isEmpty()){return true;}int i2 = deque.peek();if(i2 >= i1){return false;}}return true;}private void midTraverse(TreeNode node) {if (node == null) {return;}midTraverse(node.left);deque.push(node.val);midTraverse(node.right);}
}
