搜索

https://leetcode-cn.com/problems/search-in-a-binary-search-tree/

  1. class Solution {
  2.     public TreeNode searchBST(TreeNode root, int val) {
  3.         while(root != null){
  4.             if(val < root.val)
  5.                 root = root.left;
  6.             else if(val > root.val)
  7.                 root = root.right;
  8.             else return root;
  9.         }
  10.         return null;
  11.     }
  12. }

插入

https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

  1. class Solution {
  2.     public TreeNode insertIntoBST(TreeNode root, int val) {
  3.         TreeNode r = root;
  4.         if(r == null)
  5.             r = new TreeNode(val);
  6.         while(root != null){
  7.             if(val < root.val){
  8.                 if(root.left == null){
  9.                     root.left = new TreeNode(val);
  10.                     break;
  11.                 }                   
  12.                 else root = root.left;
  13.             }
  14.             else{
  15.                 if(root.right == null){
  16.                     root.right = new TreeNode(val);
  17.                     break;
  18.                 }                   
  19.                 else root = root.right;
  20.             }
  21.         }
  22.         return r;
  23.     }
  24. }

删除

https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/

  1. class Solution {
  2.     public TreeNode deleteNode(TreeNode root, int key) {
  3.         if(root == null)
  4.             return null;
  5.         else if(key < root.val)
  6.             root.left = deleteNode(root.left, key);
  7.         else if(key > root.val)
  8.             root.right = deleteNode(root.right, key);
  9.         else{
  10.             if(root.left != null && root.right != null){
  11.                 //两边都有子树，在左子树中找最大值
  12.                 TreeNode temp = findMax(root.left);
  13.                 root.val = temp.val;
  14.                 //删除找到的最大节点
  15.                 root.left = deleteNode(root.left, root.val);
  16.             }
  17.             else{
  18.                 //有一边为空
  19.                 TreeNode temp = root;
  20.                 if(root.left == null)
  21.                     root = root.right;
  22.                 else if(root.right == null)
  23.                     root = root.left;
  24.             }
  25.         }
  26.         return root;
  27.     }
  29.     public TreeNode findMax(TreeNode root){
  30.         while(root.right != null)
  31.             root = root.right;
  32.         return root;
  33.     }
  34. }