[LintCode] Insert Node in a Binary Search Tree

Taste 發布于2019-08-14 15:33 / 511人閱讀

摘要：建立兩個樹結點，先用找到在的位置，讓作為的根節點找到的位置后，指向。此時，用代替與連接就可以了。

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

云服務器 GPU云服務器 binary-search-tree binary-tree binary-search LintCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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