Leetcode刷题笔记 701. 二叉搜索树中的插入操作

知识点：二叉树、递归、非递归 时间：2020年9月30日 题目链接：

题目 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

示例1 输入：

给定二叉搜索树:
	
	        4
	       / 
	      2   7
	     / 
	    1   3
	
	和 插入的值: 5

输出：

你可以返回这个二叉搜索树:
	
	         4
	       /   
	      2     7
	     /    /
	    1   3 5
	或者这个树也是有效的:
	
	         5
	       /   
	      2     7
	     /    
	    1   3
	         
	          4

提示:

1. 给定的树上的节点数介于 0 和 10^4 之间
2. 每个节点都有一个唯一整数值，取值范围从 0 到 10^8
3. -10^8 <= val <= 10^8
4. 新值和原始二叉搜索树中的任意节点值都不同

思路 方法1:

1. 递归，找到应该放入的地方
2. 如果是空的话就返回，
3. 左边子树=新函数返回的子树，右子树=新函数返回的子树

方法2:

1. 非递归，也是找放的位置
2. 如果该放的位置为空就放，否则，继续找

代码

#include <stdio.h>
#include <iostream>
using namespace std;
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 == nullptr)
            return new TreeNode(val);
        if(root->val > val)
            root->left = insertIntoBST(root->left, val);
        else
            root->right = insertIntoBST(root->right, val);
        return  root;
    }
};
*/
class Solution {
          
   
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
          
   
        if(root == nullptr)
            return new TreeNode(val);
        TreeNode* tmp = root;
        while(tmp != nullptr){
          
   
            if(val < tmp->val){
          
   
                if(tmp->left==nullptr){
          
   
                    tmp->left = new TreeNode(val);
                    break;
                }else
                    tmp = tmp ->left;
            }else{
          
   
                if(tmp->right==nullptr){
          
   
                    tmp->right = new TreeNode(val);
                    break;
                }else
                    tmp = tmp ->right;
            }
        }
        return root;
    }
};
void print_tree(TreeNode* root){
          
   
    if(root==nullptr)
        return;
    print_tree(root->left);
    cout<<root->val<<endl;
    print_tree(root->right);
}
int main()
{
          
   
    TreeNode node1(1);TreeNode node2(3);
    TreeNode node3(2, &node1, &node2);
    TreeNode node4(7);
    TreeNode root(4, &node3, &node4);
    print_tree(&root);
    Solution s;
    TreeNode *ans = s.insertIntoBST(&root, 5);
    print_tree(ans);
    return 0;
}

今天也是爱zz的一天哦！