LeetBook- 二叉搜索树
以上是LeetCode的二叉搜索树的分类题目,总结起来就是利用二叉搜索树的中序遍历是升序的进行各种变式,其中:
例 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 int successor(TreeNode root){ root = root.right; while(root.left != null){ root = root.left; } return root.val; } public int predecessor(TreeNode root){ root = root.left; while(root.right != null){ root = root.right; } return root.val; } public TreeNode deleteNode(TreeNode root, int key) { if(root == null){ return null; } if(key > root.val){ root.right = deleteNode(root.right,key); }else if(key < root.val){ root.left = deleteNode(root.left,key); }else{ if(root.left == null && root.right == null){ root = null; } else if(root.right != null){ root.val = successor(root); root.right = deleteNode(root.right,root.val); } else{ root.val = predecessor(root); root.left = deleteNode(root.left,root.val); } } return root; } }