###### tags: `Leetcode` `medium` `tree` `python` `c++`

# 701. Insert into a Binary Search Tree

## [題目連結:] https://leetcode.com/problems/insert-into-a-binary-search-tree/

## 題目:
You are given the ```root``` node of a binary search tree (BST) and a ```value``` to insert into the tree. Return the root node of the BST after the insertion. It is **guaranteed** that the new value does not exist in the original BST.

**Notice** 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**.


## 解體想法:
* 此題為在BST中插入給定節點，使其仍保持BST性質
* 解法:
* 比較與當前root.val，遞歸即可

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def insertIntoBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root:
            return TreeNode(val)
        if val>root.val:
            root.right=self.insertIntoBST(root.right,val)
        else:
            root.left=self.insertIntoBST(root.left,val)
        return root

root=TreeNode(4)
res=Solution()
res.insertIntoBST(root,2)
res.insertIntoBST(root,7)
res.insertIntoBST(root,1)
res.insertIntoBST(root,3)
root.printTree()

## C++:

#include<bits/stdc++.h>
using namespace std;

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