[LintCode] Insert Node in a Binary Search Tree

Taste 发布于2019-08-14 15:33 / 356人阅读

摘要：建立两个树结点，先用找到在的位置，让作为的根节点找到的位置后，指向。此时，用代替与连接就可以了。

Problem

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree.

Example

Given binary search tree as follow, after Insert node 6, the tree should be:

  2             2
 /            / 
1   4   -->   1   4
   /             /  
  3             3   6

Challenge

Can you do it without recursion?

Note

建立两个树结点，先用cur找到node在BST的位置，让pre作为cur的根节点；找到node的位置后，cur指向null。此时，用node代替cur与pre连接就可以了。返回root。

Solution

public class Solution {
    public TreeNode insertNode(TreeNode root, TreeNode node) {
        if (root == null) return node;
        TreeNode cur = root, pre = null;
        while (cur != null) {
            pre = cur;
            if (cur.val > node.val) cur = cur.left;
            else cur = cur.right;
        }
        if (pre != null) {
            if (pre.val > node.val) pre.left = node;
            else pre.right = node;
        }
        return root;
    }
}

私有云海外云主机 binary-search-tree binary-tree binary-search LintCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65844.html

[LintCode] Remove Node in Binary Search Tree [理解BS

Problem Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You sho...

陈江龙 2019-08-14 15:33 评论0 收藏0
[LintCode] Binary Search Tree Iterator

摘要：建立一个堆栈，先将最左边的结点从大到小压入栈，这样的话，为了实现迭代即返回下一个的函数就要考虑右边的结点。如此，实现函数。 Problem Design an iterator over a binary search tree with the following rules: Elements are visited in ascending order (i.e. an in-o...

silencezwm 2019-08-14 15:33 评论0 收藏0
[LintCode] Search Range in Binary Search Tree

摘要：重点是根据的性质，先左后根最后右。另一重点是，函数和函数都要用的的参数，记得在函数外层定义。 Problem Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. pr...

draveness 2019-08-14 15:12 评论0 收藏0
[LintCode] Check Full Binary Tree

Description A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Conversely, there is no node in a full binary tree, which has one child node. More in...

Keven 2019-08-15 17:46 评论0 收藏0
[LintCode/LeetCode] Lowest Common Ancestor of BST/

摘要：递归左右子树，若左右子树都有解，那么返回根节点若仅左子树有解，返回左子树若仅右子树有解，返回右子树若都无解，返回。对于而言，更为简单公共祖先一定是大于等于其中一个结点，小于等于另一个结点。 Problem Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the ...

dinfer 2019-08-14 15:33 评论0 收藏0