48 Insert into a Binary Search Tree

devi

发布于 2021-08-18 16:19:24

26100

代码可运行

文章被收录于专栏：搬砖记录搬砖记录

运行总次数：0

代码可运行

题目

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,

Given the tree:

And the value to insert: 5

You can return this binary search tree:

This tree is also valid:

分析

题意：把一个新值查到二叉搜索树中，返回的树满足二叉搜索树的规则即可。

最简单的方法，递归遍历吧。

如果新值比当前节点大，递归右子树
如果新值比当前节点小，递归左子树
如果当前节点为空，则将新值作为节点接到当前节点。

解答

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null)
            return new TreeNode(val);
        if(val>root.val)
            root.right = insertIntoBST(root.right,val);
        else
            root.left = insertIntoBST(root.left,val);
        return root;
    }
}

速度可以，但是递归非常耗内存。去瞅瞅别人的解法。

拆开递归运行性能也差不多，这里贴出来作为参考。

    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        TreeNode cur = root;
        while(true) {
            if(cur.val <= val) {
                if(cur.right != null) cur = cur.right;
                else {
                    cur.right = new TreeNode(val);
                    break;
                }
            } else {
                if(cur.left != null) cur = cur.left;
                else {
                    cur.left = new TreeNode(val);
                    break;
                }
            }
        }
        return root;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/03/13 ，如有侵权请联系 cloudcommunity@tencent.com 删除

sql