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

陈江龙发布于2019-08-14 15:33 / 2122人阅读

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

混合云私有云 binary-search-tree binary-tree binary-search LintCode

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

转载请注明本文地址：https://www.ucloud.cn/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