二叉搜索树的插入

题目描述

力扣链接🔗

代码思路

根据二叉树的性质，进行搜索，由于插入在叶子节点，搜索到最后进行插入。

有返回值的递归

有返回值的递归，在添加时可以直接进行返回，最后会递归到root。

/**
 * 有返回值的递归法
 *
 * @param root
 * @param val
 * @return
 */
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) { // 当节点为空时，此时就该赋值了
        TreeNode treeNode = new TreeNode(val);
        return treeNode;
    }
    if (root.val > val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

无返回值的递归

无返回值递归需要记录上一次的节点，在进行添加。（因为不像有返回值递归可以直接返回到根节点）

/**
 * 无返回值的递归法
 *
 * @param root
 * @param val
 * @return
 */
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    traversal(root, val);
    return root;
}
TreeNode parent;    // 用来记录上一个节点
public void traversal(TreeNode cur, int val) {
    if (cur == null) {  // 当到达最后时，需要用上一个节点来赋值
        TreeNode node = new TreeNode(val);
        if (parent.val > val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        return;
    }
    parent = cur;
    if (cur.val > val) traversal(cur.left, val);
    if (cur.val < val) traversal(cur.right, val);
    return;
}

迭代法

迭代法也需要记录上一次的节点，在进行添加。

/**
 * 迭代法
 *
 * @param root
 * @param val
 * @return
 */
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    TreeNode cur = root;
    // 记录上一个节点进行赋值
    TreeNode parent = root;
    while (cur != null) {
        parent = cur;   // 需要放在最前面，最后一轮时，在最底层
        if (cur.val > val) {
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    if (parent.val > val) {
        parent.left = new TreeNode(val);
    } else {
        parent.right = new TreeNode(val);
    }
    return root;
}