题目

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

代码与解析

说实话,这道题刚看到,想到一个很蠢的办法:遍历二叉搜索树,然后将值存入数组,然后将盖val插入数组,后排序,或者直接中序遍历,然后将值插入数组,然后根据该数组生成二叉搜索树。

实际上这道题可以更简单,可以用递归法
递归三部曲:

  • 确定参数及返回值,
    要传入根节点指针,要插入元素,返回新插入节点指针

  • 确定终止条件
    如果遇到空节点,说明这里就是要插的位置,
    具体原因可以参考一下carl大佬的博客::点我::
    这里讲解的很好,有很多种插入的方式,
    这里贴一下go语言实现:

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

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
}
分类: 算法

站点统计

  • 文章总数:315 篇
  • 分类总数:20 个
  • 标签总数:193 个
  • 运行天数:1147 天
  • 访问总数:26753 人次

浙公网安备33011302000604

辽ICP备20003309号