LeetCode 701 Insert into a Binary Search Tree

Tag: 二叉搜索树 LeetCode Posted on 2022-02-07 13:05:11 Edited on 2022-02-07 13:15:32 Views: 170

概述

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

迭代法

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

  1. 可以作为叶节点插入,
  2. 也可以作为父节点插入。

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

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/