LeetCode 701 Insert into a Binary Search Tree

概述

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

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

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