LeetCode 701 Insert into a Binary Search Tree

    
        标签：
        
            二叉搜索树
        
            LeetCode
        
    发布于：2022-02-07 13:05:11
    编辑于：2022-02-07 13:15:32
    浏览量：967

概述

https://leetcode.com/problems/insert-into-a-binary-search-tree/

递归法

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;
    }
};

迭代法

新节点的插入位置不是唯一的：

可以作为叶节点插入，
也可以作为父节点插入。

简单起见，这里选第一种插入方式。那么我们就需要找到一个合适的叶节点或只有一个子节点的节点，令其做新节点的父节点。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        auto node = new TreeNode(val);
        if (!root) return node;
        auto c = root;
        while (true) {
            if (c->val > val) {
                if (c->left) {
                    c = c->left;
                } else {
                    c->left = node;
                    break;
                }
            } else {
                if (c->right) {
                    c = c->right;
                } else {
                    c->right = node;
                    break;
                }
            }
        }
        return root;
    }
};

Links: leetcode-701-insert-into-a-binary-search-tree