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

陳江龍發布于2019-08-14 15:33 / 2252人閱讀

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:

Remove 3, you can either return:

Note

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

(1)

            root
            /  
        left    right
        /      /   
       x    l  r     x

(2)

    left            right
    /              /   
   x               r     x
                  /
                 l

(3)

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

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65848.html

[LintCode] Insert Node in a Binary Search Tree

摘要：建立兩個樹結點，先用找到在的位置，讓作為的根節點找到的位置后，指向。此時，用代替與連接就可以了。 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 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/LeetCode] Binary Tree Serialization

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

keithyau 2019-08-14 15:12 評論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