Skip to content

Latest commit

 

History

History
730 lines (609 loc) · 20.4 KB

0701.二叉搜索树中的插入操作.md

File metadata and controls

730 lines (609 loc) · 20.4 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

701.二叉搜索树中的插入操作

力扣题目链接

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

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

701.二叉搜索树中的插入操作

提示：

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

算法公开课

《代码随想录》算法视频公开课：原来这么简单？ | LeetCode：701.二叉搜索树中的插入操作，相信结合视频在看本篇题解，更有助于大家对本题的理解。

思路

这道题目其实是一道简单题目，但是题目中的提示：有多种有效的插入方式，还可以重构二叉搜索树，一下子吓退了不少人，瞬间感觉题目复杂了很多。

其实可以不考虑题目中提示所说的改变树的结构的插入方式。

如下演示视频中可以看出：只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。

701.二叉搜索树中的插入操作

例如插入元素10 ，需要找到末尾节点插入便可，一样的道理来插入元素15，插入元素0，插入元素6，需要调整二叉树的结构么？ 并不需要。。

只要遍历二叉搜索树，找到空节点 插入元素就可以了，那么这道题其实就简单了。

接下来就是遍历二叉搜索树的过程了。

递归

递归三部曲：

  • 确定递归函数参数以及返回值

参数就是根节点指针，以及要插入元素，这里递归函数要不要有返回值呢？

可以有，也可以没有，但递归函数如果没有返回值的话，实现是比较麻烦的，下面也会给出其具体实现代码。

有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作。（下面会进一步解释）

递归函数的返回类型为节点类型TreeNode * 。

代码如下：

TreeNode* insertIntoBST(TreeNode* root, int val)
  • 确定终止条件

终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。

代码如下：

if (root == NULL) {
    TreeNode* node = new TreeNode(val);
    return node;
}

这里把添加的节点返回给上一层，就完成了父子节点的赋值操作了，详细再往下看。

  • 确定单层递归的逻辑

此时要明确，需要遍历整棵树么？

别忘了这是搜索树，遍历整棵搜索树简直是对搜索树的侮辱。

搜索树是有方向了，可以根据插入元素的数值，决定递归方向。

代码如下：

if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;

到这里，大家应该能感受到，如何通过递归函数返回值完成了新加入节点的父子关系赋值操作了，下一层将加入节点返回，本层用root->left或者root->right将其接住。

整体代码如下：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if (root->val > val) root->left = insertIntoBST(root->left, val);
        if (root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};

可以看出代码并不复杂。

刚刚说了递归函数不用返回值也可以，找到插入的节点位置，直接让其父节点指向插入节点，结束递归，也是可以的。

那么递归函数定义如下：

TreeNode* parent; // 记录遍历节点的父节点
void traversal(TreeNode* cur, int val)

没有返回值，需要记录上一个节点（parent），遇到空节点了，就让parent左孩子或者右孩子指向新插入的节点。然后结束递归。

代码如下：

class Solution {
private:
    TreeNode* parent;
    void traversal(TreeNode* cur, int val) {
        if (cur == NULL) {
            TreeNode* node = new TreeNode(val);
            if (val > parent->val) parent->right = node;
            else parent->left = node;
            return;
        }
        parent = cur;
        if (cur->val > val) traversal(cur->left, val);
        if (cur->val < val) traversal(cur->right, val);
        return;
    }

public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        parent = new TreeNode(0);
        if (root == NULL) {
            root = new TreeNode(val);
        }
        traversal(root, val);
        return root;
    }
};

可以看出还是麻烦一些的。

我之所以举这个例子，是想说明通过递归函数的返回值完成父子节点的赋值是可以带来便利的。

网上千篇一律的代码，可能会误导大家认为通过递归函数返回节点 这样的写法是天经地义，其实这里是有优化的！

迭代

再来看看迭代法，对二叉搜索树迭代写法不熟悉，可以看这篇：二叉树：二叉搜索树登场！

在迭代法遍历的过程中，需要记录一下当前遍历的节点的父节点，这样才能做插入节点的操作。

在二叉树：搜索树的最小绝对差和二叉树：我的众数是多少？中，都是用了记录pre和cur两个指针的技巧，本题也是一样的。

代码如下：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        TreeNode* cur = root;
        TreeNode* parent = root; // 这个很重要，需要记录上一个节点，否则无法赋值新节点
        while (cur != NULL) {
            parent = cur;
            if (cur->val > val) cur = cur->left;
            else cur = cur->right;
        }
        TreeNode* node = new TreeNode(val);
        if (val < parent->val) parent->left = node;// 此时是用parent节点的进行赋值
        else parent->right = node;
        return root;
    }
};

总结

首先在二叉搜索树中的插入操作，大家不用恐惧其重构搜索树，其实根本不用重构。

然后在递归中，我们重点讲了如何通过递归函数的返回值完成新加入节点和其父节点的赋值操作，并强调了搜索树的有序性。

最后依然给出了迭代的方法，迭代的方法就需要记录当前遍历节点的父节点了，这个和没有返回值的递归函数实现的代码逻辑是一样的。

其他语言版本

Java

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode newRoot = root;
        TreeNode pre = root;
        while (root != null) {
            pre = root;
            if (root.val > val) {
                root = root.left;
            } else if (root.val < val) {
                root = root.right;
            } 
        }
        if (pre.val > val) {
            pre.left = new TreeNode(val);
        } else {
            pre.right = new TreeNode(val);
        }

        return newRoot;
    }
}

递归法

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
            return new TreeNode(val);
            
        if (root.val < val){
            root.right = insertIntoBST(root.right, val); // 递归创建右子树
        }else if (root.val > val){
            root.left = insertIntoBST(root.left, val); // 递归创建左子树
        }
        return root;
    }
}

Python

递归法（版本一）

class Solution:
    def __init__(self):
        self.parent = None

    def traversal(self, cur, val):
        if cur is None:
            node = TreeNode(val)
            if val > self.parent.val:
                self.parent.right = node
            else:
                self.parent.left = node
            return

        self.parent = cur
        if cur.val > val:
            self.traversal(cur.left, val)
        if cur.val < val:
            self.traversal(cur.right, val)

    def insertIntoBST(self, root, val):
        self.parent = TreeNode(0)
        if root is None:
            return TreeNode(val)
        self.traversal(root, val)
        return root

递归法（版本二）

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None or root.val == val:
            return TreeNode(val)
        elif root.val > val:
            if root.left is None:
                root.left = TreeNode(val)
            else:
                self.insertIntoBST(root.left, val)
        elif root.val < val:
            if root.right is None:
                root.right = TreeNode(val)
            else:
                self.insertIntoBST(root.right, val)
        return root

递归法（版本三）

class Solution:
    def insertIntoBST(self, root, val):
        if root is None:
            node = TreeNode(val)
            return node

        if root.val > val:
            root.left = self.insertIntoBST(root.left, val)
        if root.val < val:
            root.right = self.insertIntoBST(root.right, val)

        return root

迭代法（版本一）

class Solution:
    def insertIntoBST(self, root, val):
        if root is None:  # 如果根节点为空，创建新节点作为根节点并返回
            node = TreeNode(val)
            return node

        cur = root
        parent = root  # 记录上一个节点，用于连接新节点
        while cur is not None:
            parent = cur
            if cur.val > val:
                cur = cur.left
            else:
                cur = cur.right

        node = TreeNode(val)
        if val < parent.val:
            parent.left = node  # 将新节点连接到父节点的左子树
        else:
            parent.right = node  # 将新节点连接到父节点的右子树

        return root

迭代法（版本二）

class Solution:
    def insertIntoBST(self, root, val):
        if root is None:
            return TreeNode(val)
        parent = None
        cur = root
        while cur:
            parent = cur
            if val < cur.val:
                cur = cur.left
            else:
                cur = cur.right
        if val < parent.val:
            parent.left = TreeNode(val)
        else:
            parent.right = TreeNode(val)
        return root

迭代法（精简）

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root: # 如果根节点为空，创建新节点作为根节点并返回
            return TreeNode(val)
        cur = root
        while cur:
            if val < cur.val:
                if not cur.left: # 如果此时父节点的左子树为空
                    cur.left = TreeNode(val) # 将新节点连接到父节点的左子树
                    return root
                else:
                    cur = cur.left
            elif val > cur.val:
                if not cur.right: # 如果此时父节点的左子树为空
                    cur.right = TreeNode(val) # 将新节点连接到父节点的右子树
                    return root
                else:
                    cur = cur.right

Go

递归法

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        root = &TreeNode{Val: val}
        return root
    }
    if root.Val > val {
        root.Left = insertIntoBST(root.Left, val)
    } else {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}

迭代法

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val:val}
    }
    node := root
    var pnode *TreeNode
    for node != nil {
        if val > node.Val {
            pnode = node
            node = node.Right
        } else {
            pnode = node
            node = node.Left
        }
    }
    if val > pnode.Val {
        pnode.Right = &TreeNode{Val: val}
    } else {
        pnode.Left = &TreeNode{Val: val}
    }
    return root
}

JavaScript

有返回值的递归写法

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function (root, val) {
    const setInOrder = (root, val) => {
        if (root === null) {
            let node = new TreeNode(val);
            return node;
        }
        if (root.val > val)
            root.left = setInOrder(root.left, val);
        else if (root.val < val)
            root.right = setInOrder(root.right, val);
        return root;
    }
    return setInOrder(root, val);
};

无返回值的递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function (root, val) {
    let parent = new TreeNode(0);
    const preOrder = (cur, val) => {
        if (cur === null) {
            let node = new TreeNode(val);
            if (parent.val > val)
                parent.left = node;
            else
                parent.right = node;
            return;
        }
        parent = cur;
        if (cur.val > val)
            preOrder(cur.left, val);
        if (cur.val < val)
            preOrder(cur.right, val);
    }
    if (root === null)
        root = new TreeNode(val);
    preOrder(root, val);
    return root;
};

迭代

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function (root, val) {
    if (root === null) {
        root = new TreeNode(val);
    } else {
        let parent = new TreeNode(0);
        let cur = root;
        while (cur) {
            parent = cur;
            if (cur.val > val)
                cur = cur.left;
            else
                cur = cur.right;
        }
        let node = new TreeNode(val);
        if (parent.val > val)
            parent.left = node;
        else
            parent.right = node;
    }
    return root;
};

TypeScript

递归-有返回值

function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
    if (root === null) return new TreeNode(val);
    if (root.val > val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
};

递归-无返回值

function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
    if (root === null) return new TreeNode(val);
    function recur(root: TreeNode | null, val: number) {
        if (root === null) {
            if (parentNode.val > val) {
                parentNode.left = new TreeNode(val);
            } else {
                parentNode.right = new TreeNode(val);
            }
            return;
        }
        parentNode = root;
        if (root.val > val) recur(root.left, val);
        if (root.val < val) recur(root.right, val);
    }
    let parentNode: TreeNode = root;
    recur(root, val);
    return root;
};

迭代法

function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
    if (root === null) return new TreeNode(val);
    let curNode: TreeNode | null = root;
    let parentNode: TreeNode = root;
    while (curNode !== null) {
        parentNode = curNode;
        if (curNode.val > val) {
            curNode = curNode.left
        } else {
            curNode = curNode.right;
        }
    }
    if (parentNode.val > val) {
        parentNode.left = new TreeNode(val);
    } else {
        parentNode.right = new TreeNode(val);
    }
    return root;
};

Scala

递归:

object Solution {
  def insertIntoBST(root: TreeNode, `val`: Int): TreeNode = {
    if (root == null) return new TreeNode(`val`)
    if (`val` < root.value) root.left = insertIntoBST(root.left, `val`) 
    else root.right = insertIntoBST(root.right, `val`)
    root  // 返回根节点
  }
}

迭代:

object Solution {
  def insertIntoBST(root: TreeNode, `val`: Int): TreeNode = {
    if (root == null) {
      return new TreeNode(`val`)
    }
    var parent = root   // 记录当前节点的父节点
    var curNode = root
    while (curNode != null) {
      parent = curNode
      if(`val` < curNode.value) curNode = curNode.left
      else curNode = curNode.right
    }
    if(`val` < parent.value) parent.left = new TreeNode(`val`)
    else parent.right = new TreeNode(`val`)
    root  // 最终返回根节点
  }
}

Rust

迭代：

impl Solution {
    pub fn insert_into_bst(
        root: Option<Rc<RefCell<TreeNode>>>,
        val: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if root.is_none() {
            return Some(Rc::new(RefCell::new(TreeNode::new(val))));
        }
        let mut cur = root.clone();
        let mut pre = None;
        while let Some(node) = cur.clone() {
            pre = cur;
            if node.borrow().val > val {
                cur = node.borrow().left.clone();
            } else {
                cur = node.borrow().right.clone();
            };
        }
        let r = Some(Rc::new(RefCell::new(TreeNode::new(val))));
        let mut p = pre.as_ref().unwrap().borrow_mut();
        if val < p.val {
            p.left = r;
        } else {
            p.right = r;
        }

        root
    }
}

递归：

impl Solution {
    pub fn insert_into_bst(
        root: Option<Rc<RefCell<TreeNode>>>,
        val: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = &root {
            if node.borrow().val > val {
                let left = Self::insert_into_bst(node.borrow_mut().left.take(), val);
                node.borrow_mut().left = left;
            } else {
                let right = Self::insert_into_bst(node.borrow_mut().right.take(), val);
                node.borrow_mut().right = right;
            }
            root
        } else {
            Some(Rc::new(RefCell::new(TreeNode::new(val))))
        }
    }
}

C#

// 递归
public TreeNode InsertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);

    if (root.val > val) root.left = InsertIntoBST(root.left, val);
    if (root.val < val) root.right = InsertIntoBST(root.right, val);
    return root;
}