木又的第154篇leetcode解题报告
二叉树
类型第44篇解题报告
leetcode第701题:二叉搜索树中的插入操作
https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
【题目】
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。
例如,
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和 插入的值: 5
你可以返回这个二叉搜索树:
4
/ \
2 7
/ \ /
1 3 5
或者这个树也是有效的:
5
/ \
2 7
/ \
1 3
\
4
【思路】
本题较为简单,考虑最简单的插入方式,将插入节点作为叶子节点。
遍历节点node,并记录其父节点parent。当node为空,则比较parent->val和val的大小,parent->val较大时,则插入节点作为parent节点的左孩子,parent->val较小时,插入节点作为parent节点的右孩子;当node->val > val,则继续访问左子树(parent = node, node = node->left);node->val < val,继续访问右子树(parent = node, node = node->right)。
【代码】
python版本
# 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)
parent = root
node = root
while node:
parent = node
if node.val > val:
node = node.left
else:
node = node.right
# insert
if parent.val > val:
parent.left = TreeNode(val)
else:
parent.right = TreeNode(val)
return root
C++版本
/**
* 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) {
TreeNode* parent = root;
TreeNode* node = root;
if(!root){
parent = new TreeNode(val);
return parent;
}
// serach
while(node){
parent = node;
if(node->val > val)
node = node->left;
else
node = node->right;
}
// insert
if(parent->val > val)
parent->left = new TreeNode(val);
else
parent->right = new TreeNode(val);
return root;
}
};