LeetCode二叉搜索树相关高频题（十四）

大家好，我是方圆 无它，唯手熟尔

题号

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

98. 验证二叉搜索树

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { long pre = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if(root == null){ return true; } //遍历左子树 if(!isValidBST(root.left)){ return false; } //判断当前节点与前一个节点的值 //我们采用的是中序遍历，要求符合前一个值小于当前值 if(root.val <= pre){ return false; } pre = root.val; //遍历右子树 return isValidBST(root.right); } }

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; } }

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

/** * 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 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; } }

---

简简单单也要多练呐！