Remove Node in Binary Search Tree

今天是一道題目，來自LintCode，難度為Hard，Acceptance為25%。

題目如下

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

解題思路及代碼見閱讀原文

回復0000查看更多題目

解題思路

首先，該題在《算法導論》一書中是有的。思路也較為容易理解，關鍵是實現(xiàn)算法時需要注意的各種細節(jié)。

那么下面說明該題的思路：

第一步，當然是找到要刪除的節(jié)點node和它的父節(jié)點parent，這里采用前序遍歷即可。如題目中所說，如果找到了就繼續(xù)，否則什么都不做，直接返回。

第二步，就是刪除該node節(jié)點，這里分為兩種情況：

• node節(jié)點的右子樹不存在。此時，直接用parent節(jié)點的子節(jié)點指向該node節(jié)點的左節(jié)點。

• node節(jié)點的右子樹存在。此時，需要找到右子樹的最小節(jié)點，用該節(jié)點替換node節(jié)點。

技巧：
因為要刪除的節(jié)點可能是根節(jié)點，因此為了算法的通用性，可以首先new一個dummy節(jié)點，該節(jié)點的左節(jié)點指向根節(jié)點，這樣處理起來更為方便。

最后，我們來看代碼。

代碼如下

Java版

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    public TreeNode removeNode(TreeNode root, int value) {
        TreeNode dummy = new TreeNode(0);
        dummy.left = root;
        
        TreeNode parent = findNode(dummy, root, value);
        TreeNode node;
        if (parent.left != null && parent.left.val == value) {
            node = parent.left;
        } else if (parent.right != null && parent.right.val == value) {
            node = parent.right;
        } else {
            return dummy.left;
        }
        
        deleteNode(parent, node);
        
        return dummy.left;
    }
    
    private TreeNode findNode(TreeNode parent, TreeNode node, int value) {
        if (node == null) {
            return parent;
        }
        
        if (node.val == value) {
            return parent;
        }
        if (value < node.val) {
            return findNode(node, node.left, value);
        } else {
            return findNode(node, node.right, value);
        }
    }
    
    private void deleteNode(TreeNode parent, TreeNode node) {
        if (node.right == null) {
            if (parent.left == node) {
                parent.left = node.left;
            } else {
                parent.right = node.left;
            }
        } else {
            TreeNode temp = node.right;
            TreeNode father = node;
            
            while (temp.left != null) {
                father = temp;
                temp = temp.left;
            }
            
            if (father.left == temp) {
                father.left = temp.right;
            } else {
                father.right = temp.right;
            }
            
            if (parent.left == node) {
                parent.left = temp;
            } else {
                parent.right = temp;
            }
            
            temp.left = node.left;
            temp.right = node.right;
        }
    }
}

關注我
該公眾號會每天推送常見面試題，包括解題思路是代碼，希望對找工作的同學有所幫助

image