二叉搜索树相关

701. 二叉搜索树中的插入操作98. 验证二叉搜索树450. 删除二叉搜索树中的节点

---

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

class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if(root==null) return new TreeNode(val); //两种情况，要么插左边，要么插右边 if(root.val<val) root.right=insertIntoBST(root.right,val); else{ root.left=insertIntoBST(root.left,val); } return root; } }

98. 验证二叉搜索树

1.递归 class Solution { long min= Long.MIN_VALUE; //一定要定义全局变量 public boolean isValidBST(TreeNode root) { if(root==null) return true; if(!isValidBST(root.left)){ //左 return false; }; if(root.val<=min) return false; //中 min=root.val; return isValidBST(root.right) ; //右 } } 2.迭代 class Solution { Stack<TreeNode> q=new Stack<>(); List<Integer> res=new ArrayList<>(); long min=-Long.MAX_VALUE; public boolean isValidBST(TreeNode root) { while(!q.isEmpty()||root!=null){ while(root!=null){ q.add(root); root=root.left; //左 } root=q.pop(); if(root.val<=min) return false; //中 min=root.val; root=root.right; //右 } return true; } }

450. 删除二叉搜索树中的节点

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode deleteNode(TreeNode root, int key) { if(root == null){ return null; } //当前节点的值大于key if(root.val > key){ root.left = deleteNode(root.left,key); }else if(root.val < key){ //当前节点值小于key root.right = deleteNode(root.right,key); }else{ //找到key值 //没有左节点的情况 if(root.left == null){ return root.right; }else if(root.right == null){ //没有右节点的情况 return root.left; }else{ //两节点都有的情况 TreeNode temp = root.right; //遍历左子树 while(temp.left != null){ temp = temp.left; } temp.left = root.left; return root.right; } } return root; } }