成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode] Insert Node in a Binary Search Tree

Taste / 517人閱讀

摘要：建立兩個(gè)樹結(jié)點(diǎn)，先用找到在的位置，讓作為的根節(jié)點(diǎn)找到的位置后，指向。此時(shí)，用代替與連接就可以了。

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

建立兩個(gè)樹結(jié)點(diǎn)，先用cur找到node在BST的位置，讓pre作為cur的根節(jié)點(diǎn)；找到node的位置后，cur指向null。此時(shí)，用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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65844.html

相關(guān)文章

  • [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...

    陳江龍 評論0 收藏0

  • [LintCode] Binary Search Tree Iterator

    摘要：建立一個(gè)堆棧，先將最左邊的結(jié)點(diǎn)從大到小壓入棧，這樣的話，為了實(shí)現(xiàn)迭代即返回下一個(gè)的函數(shù)就要考慮右邊的結(jié)點(diǎn)。如此，實(shí)現(xiàn)函數(shù)。 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 評論0 收藏0

  • [LintCode] Search Range in Binary Search Tree

    摘要：重點(diǎn)是根據(jù)的性質(zhì)，先左后根最后右。另一重點(diǎn)是，函數(shù)和函數(shù)都要用的的參數(shù)，記得在函數(shù)外層定義。 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 評論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 評論0 收藏0

  • [LintCode/LeetCode] Lowest Common Ancestor of BST/

    摘要：遞歸左右子樹，若左右子樹都有解，那么返回根節(jié)點(diǎn)若僅左子樹有解，返回左子樹若僅右子樹有解，返回右子樹若都無解，返回。對于而言，更為簡單公共祖先一定是大于等于其中一個(gè)結(jié)點(diǎn)，小于等于另一個(gè)結(jié)點(diǎn)。 Problem Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the ...

    dinfer 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<