首页 > 代码库 > LintCode-Remove node in Binary Search Tree
LintCode-Remove node in Binary Search Tree
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
Analysis:
We should consider every possible situation carefully.
Solution:
1 /** 2 * Definition of TreeNode: 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left, right; 6 * public TreeNode(int val) { 7 * this.val = val; 8 * this.left = this.right = null; 9 * }10 * }11 */12 public class Solution {13 /**14 * @param root: The root of the binary search tree.15 * @param value: Remove the node with given value.16 * @return: The root of the binary search tree after removal.17 */18 public TreeNode removeNode(TreeNode root, int value) {19 if (root==null) return null;20 21 TreeNode preRoot = new TreeNode(0);22 preRoot.left = root;23 searchNodeRecur(preRoot,root,value);24 return preRoot.left;25 }26 27 public void searchNodeRecur(TreeNode pre, TreeNode cur, int val){28 //if there is no such node, then do nothing.29 if (cur==null) return;30 31 //find the node.32 if (cur.val == val){33 removeNode(pre,cur);34 return;35 } else if (cur.val > val){36 searchNodeRecur(cur,cur.left,val);37 } else 38 searchNodeRecur(cur,cur.right,val);39 40 }41 42 public void removeNode(TreeNode pre, TreeNode cur){43 //a leaf node.44 if (cur.left==null && cur.right==null)45 if (pre.left==cur) pre.left = null;46 else pre.right = null;47 else if (cur.left==null || cur.right==null){ //cur only has one sub tree.48 TreeNode child = (cur.left==null) ? cur.right : cur.left;49 if (pre.left==cur) pre.left = child;50 else pre.right=child;51 } else { //has two sub trees, select the largest node in the left subtree52 TreeNode pre2 = cur;53 TreeNode cur2 = cur.left;54 while (cur2.right!=null){55 pre2 = cur2;56 cur2 = cur2.right;57 }58 //a leaf node59 if (cur2.left==null){60 if (pre2.left==cur2) pre2.left = null;61 else pre2.right=null;62 cur2.left = cur.left;63 cur2.right = cur.right;64 if (pre.left==cur) pre.left=cur2;65 else pre.right=cur2;66 } else {67 if (pre2.left==cur2) pre2.left = cur2.left;68 else pre2.right = cur2.left;69 cur2.left = cur.left;70 cur2.right = cur.right;71 if (pre.left==cur) pre.left=cur2;72 else pre.right=cur2;73 }74 }75 }76 77 78 79 }
LintCode-Remove node in Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。