解法一

查找过程中记得记录父节点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  * int val;
  5.  * TreeNode left;
  6.  * TreeNode right;
  7.  * TreeNode() {}
  8.  * TreeNode(int val) { this.val = val; }
  9.  * TreeNode(int val, TreeNode left, TreeNode right) {
  10.  * this.val = val;
  11.  * this.left = left;
  12.  * this.right = right;
  13.  * }
  14.  * }
  15.  */
  16. class Solution {
  17.     public TreeNode insertIntoBST(TreeNode root, int val) {
  18.         if (root == null) {
  19.             return new TreeNode(val);
  20.         }
  21.         TreeNode p = root;
  22.         TreeNode parent = root;
  23.         while (p != null) {
  24.             parent = p;
  25.             if (val > p.val) {
  26.                 p = p.right;
  27.             } else {
  28.                 p = p.left;
  29.             }
  30.         }
  31.         if (parent.val > val) {
  32.             parent.left = new TreeNode(val);
  33.         } else {
  34.             parent.right = new TreeNode(val);
  35.         }
  36.         return root;
  37.     }
  38. }