专栏首页desperate633LintCode 在二叉查找树中插入节点题目分析

LintCode 在二叉查找树中插入节点题目分析

题目

给定一棵二叉查找树和一个新的树节点,将节点插入到树中。 你需要保证该树仍然是一棵二叉查找树。

分析

分别用递归和非递归两种方法实现。本质上会发现,两种方法类似

public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param node: insert this node into the binary search tree
     * @return: The root of the new binary search tree.
     */
    public TreeNode insertNode(TreeNode root, TreeNode node) {
        if(root == null)
            return node;
            
        if(root.val > node.val)
            root.left = insertNode(root.left, node);
        else
            root.right = insertNode(root.right, node);
        
        return root;
    }
}
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param node: insert this node into the binary search tree
     * @return: The root of the new binary search tree.
     */
    public TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if (root == null) {
            root = node;
            return root;
        }
        TreeNode tmp = root;
        TreeNode last = null;
        while (tmp != null) {
            last = tmp;
            if (tmp.val > node.val) {
                tmp = tmp.left;
            } else {
                tmp = tmp.right;
            }
        }
        if (last != null) {
            if (last.val > node.val) {
                last.left = node;
            } else {
                last.right = node;
            }
        }
        return root; 
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode 克隆二叉树题目分析代码

    desperate633
  • LintCode 将二叉树拆成链表题目分析代码

    将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说,用二叉树的 right 指针,来表示链表中的 next 指针。

    desperate633
  • LintCode 验证二叉查找树题目分析代码

    2 / 1 4 / 3 5 上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.

    desperate633
  • 85. 在二叉查找树中插入节点常规操作

    You can assume there is no duplicate values in this tree + node.

    和蔼的zhxing
  • 专为程序员定制的垃圾清理工具(Node Cli实现)

    就是这个恶毒的提示,太让我烦恼了,一开始我用了腾讯的 lemon 清理工具,但是发现他并不能很好地解决我的问题,没有办法完全找出我的缓存文件。由于本人是 256...

    秋风的笔记
  • LeetCode 701: 二叉搜索树中的插入操作 Insert into a Binary Search Tree

    给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。

    爱写bug
  • PHP生成推广海报的方法

    经常有这样的需求,就是需要在生成推广海报,包含指定的二维码,分享出去别人扫码之后就可以确定用户推荐关系。

    猿哥
  • 【LeetCode 235.二叉搜索树的最近公共祖先】JavaScript/C++实现

    例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

    心谭博客
  • 从源码看redis的string结构

    redis.c 中数组 redisCommandTable 为所有暴漏出去的命令列表,以及实现命令的函数指针

    爬蜥
  • LeetCode 1019. 链表中的下一个更大节点(单调栈)

    给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为:node_1, node_2, node_3, … 。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券