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

資訊專欄INFORMATION COLUMN

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

陳江龍 / 2259人閱讀

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 should keep the tree still a binary search tree after removal.

Example

Given binary search tree:

    5
   / 
  3   6
 / 
2   4

Remove 3, you can either return:

    5
   / 
  2   6
   
    4

or

    5
   / 
  4   6
 /
2
Note

以下是rebuild的示意：先讓r到達r的最左端，然后將l接在r的左子樹，這樣就把所有比root.left大的結(jié)點都集合在root.right了。將root.right接在root.left的右子樹，然后返回root.left即可。

(1)

            root
            /  
        left    right
        /      /   
       x    l  r     x

(2)

    left            right
    /              /   
   x               r     x
                  /
                 l

(3)

            left   
            /    
           x    right
                /   
               r     x
              /  
             l
Solution 
public class Solution {
    public TreeNode removeNode(TreeNode root, int value) {
        TreeNode dummy = new TreeNode (-1), pre = dummy, cur = root;
        dummy.right = root;
        while (cur != null) {
            if (cur.val == value) {
                if(pre.left == cur) {
                    pre.left = makenew(cur);
                }
                else pre.right = makenew(cur);
                break;
            }
            else if (cur.val < value) {
                pre = cur;
                cur = cur.right;
            }
            else {
                pre = cur;
                cur = cur.left;
            }
        }
        return dummy.right;   
    }
    
    private TreeNode makenew(TreeNode node) {
        if (node.left == null || node.right == null) {
            return node.left == null ? node.right : node.left;
        }
        TreeNode left = node.left.right;
        TreeNode right = node.right.left;
        while (right.left != null) {
            right = right.left;
        }
        right.left = left;
        node.left.right = node.right;
        return node.left;
    }
}

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

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

相關(guān)文章

  • [LintCode] Insert Node in a Binary Search Tree

    摘要：建立兩個樹結(jié)點，先用找到在的位置，讓作為的根節(jié)點找到的位置后，指向。此時，用代替與連接就可以了。 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 tr...

    Taste 評論0 收藏0

  • [LintCode] Binary Search Tree Iterator

    摘要：建立一個堆棧，先將最左邊的結(jié)點從大到小壓入棧，這樣的話，為了實現(xiàn)迭代即返回下一個的函數(shù)就要考慮右邊的結(jié)點。如此，實現(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/LeetCode] Binary Tree Serialization

    摘要：這里要注意的是的用法。所以記住，用可以從自動分離出數(shù)組。跳過第一個元素并放入數(shù)組最快捷語句建立的用意記錄處理過的結(jié)點并按處理所有結(jié)點和自己的連接下面先通過判斷，再修改的符號的順序，十分巧妙更輕便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...

    keithyau 評論0 收藏0

  • [LintCode] Search Range in Binary Search Tree

    摘要：重點是根據(jù)的性質(zhì)，先左后根最后右。另一重點是，函數(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

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<