701. Insert into a Binary Search Tree

二刷 05/2022

Version #1 Iteration

一个Corner case是当root==null的时候直接返回新的点，这个一开始写错了

Time O(height)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Insert into a Binary Search Tree.

Memory Usage: 54.3 MB, less than 37.82% of Java online submissions for Insert into a Binary Search Tree.

/**

 * 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);

        }

        TreeNode prev = null, curr = root;

        while (curr != null) {

            prev = curr;

            if (curr.val > val) {

                curr = curr.left;

            } else {

                curr = curr.right;

            }

        }

        if (prev.val > val) {

            prev.left = new TreeNode(val);

        } else {

            prev.right = new TreeNode(val);

        }

        return root;

    }

}

一刷
Version #1 Straight-forward insert under leaf

98.39 %
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
TreeNode curr = root;
while (curr != null) {
if (val > curr.val) {
if (curr.right == null) {
curr.right = new TreeNode(val);
return root;
} else {
curr = curr.right;
}
} else { // val <= curr.val
if (curr.left == null) {
curr.left = new TreeNode(val);
return root;
} else {
curr = curr.left;
}
}
}
return root;
}
}