Insert into a Binary Search Tree
Tree search Binary INSERT INTO
2023-09-11 14:22:45 时间
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: 4 / \ 2 7 / \ 1 3 And the value to insert: 5
You can return this binary search tree:
4 / \ 2 7 / \ / 1 3 5
This tree is also valid:
5 / \ 2 7 / \ 1 3 \ 4
Approach #1: C++.[rescursive]
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == nullptr) root = new TreeNode(val); if (root->val > val) root->left = insertIntoBST(root->left, val); if (root->val < val) root->right = insertIntoBST(root->right, val); return root; } };
Approach #2: Java.[iterator]
/** * 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) root = 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; } }
Approach #3: Python.[recursive]
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def insertIntoBST(self, root, val): """ :type root: TreeNode :type val: int :rtype: TreeNode """ if not root: return TreeNode(val); if root.val < val: root.right = self.insertIntoBST(root.right, val) elif root.val > val: root.left = self.insertIntoBST(root.left, val) return root
相关文章
- Lintcode: Remove Node in Binary Search Tree
- Leetcode: Closest Binary Search Tree Value II
- Lintcode: Search Range in Binary Search Tree
- Leetcode: Binary Search Tree Iterator
- Leetcode: Convert Sorted Array to Binary Search Tree
- Leetcode Validate Binary Search Tree
- leetcode第一刷_Convert Sorted Array to Binary Search Tree
- BZOJ 2631 tree 动态树(Link-Cut-Tree)
- Binary Search Tree 以及一道 LeetCode 题目
- 1099 Build A Binary Search Tree (30 分)【难度: 一般 / 知识点: 建立二叉搜索树】
- [Leetcode] Convert Sorted List to Binary Search Tree
- 【LeetCode】235. Lowest Common Ancestor of a Binary Search Tree (2 solutions)
- Convert Sorted List to Binary Search Tree
- [LeetCode] Find Mode in Binary Search Tree 找二分搜索数的众数
- [LeetCode] 255. Verify Preorder Sequence in Binary Search Tree 验证二叉搜索树的先序序列
- [LeetCode] 270. Closest Binary Search Tree Value 最近的二分搜索树的值
- [LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树
- 1064 Complete Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Lowest Common Ancestor of a Binary Search Tree